16988번 Baaaaaaaaaduk2 (Easy)

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

BackTracking + BFS 문제이다.

참고로 이 코드에서 배열 크기를 1010으로 늘려, 16989번 Baaaaaaaaaduk2 (Hard) 문제에 제출하면, 시간 초과가 뜬다.

Easy 문제를 살펴보면,

simulation() 함수 안에서 MAX = max(MAX, s);는 이중 for문이 모두 끝난 뒤에 계산을 해야한다.

이는 아래의 예제를 통해 이유를 알 수 있다.(아래의 예제는 8 + 5 = 13이 나온다.)

만약 이중 for문 안에서 MAX = max(MAX, s);를 구현하면, 최댓값이 8이 나와버린다.

입력

8 6

0 0 1 2 2 2

0 0 1 2 2 2

0 1 1 0 2 2

1 2 2 0 1 1

1 2 2 1 0 0

1 2 1 0 2 0

1 1 0 0 0 1

0 1 0 0 0 0

출력

13

#include <iostream>
#include <queue>
#include <stack>
#include <cstdio>
#include <vector>
#include <cstring>
#include <string>
#include <math.h>
#include <algorithm>
#include <map>
#include <set>
#include <sstream>
#include <tuple>
 
#pragma warning(disable:4996)  
#pragma comment(linker, "/STACK:336777216")
 
using namespace std;
 
int Map[22][22] = { 0, }, N = 0, M = 0;
 
int dy[4] = { 0, 1, 0, -1 };
int dx[4] = { 1, 0, -1, 0 };
 
int MAX = 0, cnt = 0;
 
bool use[22][22] = { false, }, zero = false;
 
bool visit[22][22] = { false, };
 
void DFS(int r, int c)
{
    visit[r][c] = true;
 
    ++cnt;
 
    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 || Map[y][x] == 1 || visit[y][x]) continue;
 
        if (Map[y][x] == 2) DFS(y, x);
        
        else if (Map[y][x] == 0) zero = true; // zero가 있다고 해서, return 하면 안 된다.
    }
}
 
void simulation(int c)
{
    if (c == 2)
    {
        memset(visit, false, sizeof(visit));
 
        int s = 0;
 
        for (int i = 0; i < N; i++)
        {
            for (int j = 0; j < M; j++)
            {
                if (!visit[i][j] && Map[i][j] == 2)
                {
                    zero = false;
 
                    cnt = 0;
 
                    DFS(i, j);
 
                    if (zero) cnt = 0; // zero가 있다면 당연히 cnt를 0으로 하여, max 계산에 미적용 되게 한다.
 
                    s += cnt;
                }
            }
        }
 
        MAX = max(MAX, s);
 
        return;
    }
 
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < M; j++) 
        {
            if (!use[i][j] && Map[i][j] == 0)
            {
                Map[i][j] = 1;
                use[i][j] = true;
 
                simulation(c + 1);
 
                Map[i][j] = 0;
                use[i][j] = false;
            }
        }
    }
}
 
int main(void)
{
    MAX = -1;
 
    scanf("%d %d", &N, &M);
 
    for (int i = 0; i < N; i++) for (int j = 0; j < M; j++) scanf("%d", &Map[i][j]);
 
    simulation(0);
 
    printf("%d\n", MAX);
 
    return 0;
}