16932번 모양 만들기

https://www.acmicpc.net/problem/16932

처음에 2중 for문으로 모든 점을 탐색하여

'0'인 곳을 찾아 '1'로 바꿔 준 후 DFS를 실행하였다.

그런데 시간 초과가 떴고,

생각해보니

미리 DFS로 그룹화 시켜 그 개수를 배열에 저장해 활용하는 것이 

시간 단축에 크게 도움 되었다.

코드가 조금 복잡해 보이는 건 착각이다.

#include <iostream>
#include <queue>
#include <stack>
#include <cstdio>
#include <vector>
#include <cstring>
#include <string>
#include <math.h>
#include <algorithm>
#include <map>
#include <set>
#include <tuple>
 
#pragma warning(disable:4996)  
#pragma comment(linker, "/STACK:336777216")
 
using namespace std;
 
typedef struct info
{
    int value;
    int group;
}info;
 
info Map[1001][1001], temp;
 
int N = 0, M = 0, ans = 0, cnt = 0;
 
int dy[4] = { 0, 1, 0, -1 };
int dx[4] = { 1, 0, -1, 0 };
 
int Group[1001 * 1001] = { 0, };
 
bool visit[1001][1001] = { false, };
 
bool chk[1001 * 1001] = { false, };
 
void DFS(int r, int c, int g)
{
    Map[r][c].group = g;
    visit[r][c] = true;
 
    for (int i = 0; i < 4; i++)
    {
        int y = r + dy[i];
        int x = c + dx[i];
 
        if (y < 0 || y >= N || x < 0 || x >= M || visit[y][x] || Map[y][x].value == 0) continue;
 
        DFS(y, x, g);
        ++cnt;
    }
}
 
int onlyone()
{
    int ret = 0;
 
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < M; j++)
        {
            if (Map[i][j].value == 0) return -1;
            else if (Map[i][j].value == 1) ++ret;
        }
    }
 
    return ret;
}
 
int main(void)
{
    int num = 0;
 
    ans = -987654321;
 
    scanf("%d %d", &N, &M);
 
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < M; j++)
        {
            scanf("%d", &num);
 
            temp.value = num;
            temp.group = 0;
 
            Map[i][j] = temp;
        }
    }
 
    int oneCheck = onlyone();
 
    if (oneCheck != -1)
    {
        printf("%d\n", oneCheck);
        return 0;
    }
 
    int group = 1; // Group 전역 배열이랑 헷갈리지 말 것.
 
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < M; j++)
        {
            if (!visit[i][j] && Map[i][j].value == 1)
            {
                cnt = 1;
 
                DFS(i, j, group);
 
                Group[group++] = cnt;
            }
        }
    }
 
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < M; j++)
        {
            if (Map[i][j].value == 0)
            {
                int sum = 0;
                
                vector<int> v;
 
                for (int d = 0; d < 4; d++)
                {
                    int y = i + dy[d];
                    int x = j + dx[d];
 
                    bool stop = false; // 밑에 continue 때문에 stop은 여기서 선언
 
                    if (y < 0 || y >= N || x < 0 || x >= M || Map[y][x].value == 0) continue;
 
                    for (int k = 0; k < v.size(); k++)
                    {
                        if (Map[y][x].group == v.at(k))
                        {
                            stop = true;
                            break;
                        }
                    }
 
                    if (stop) continue;
 
                    v.push_back(Map[y][x].group);
                }
 
                for (auto a : v) sum += Group[a];
 
                ans = max(ans, sum + 1);
            }
        }
    }
 
    printf("%d\n", ans);
 
    return 0;
}