백준 14502 연구소(dfs)

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

14502번: 연구소

#include <iostream>

using namespace std;

typedef struct
{
    int x, y;
} Dir;
Dir DirMove[4] = {{-1, 0}, {1, 0}, {0, 1}, {0, -1}};

const int MAX = 8;
int graph[MAX][MAX];
int tmpGraph[MAX][MAX];
bool visited[MAX][MAX];
int N, M;
int result;
int dfsGraph[MAX][MAX];
int cnt;

void dfs(int x, int y)
{
    visited[x][y] = 1;
    for (int n = 0; n < 4; n++)
    {
        int nextX = x + DirMove[n].x;
        int nextY = y + DirMove[n].y;
        if (0 <= nextX && nextX < N && 0 <= nextY && nextY < M && dfsGraph[nextX][nextY] == 0 && !visited[nextX][nextY])
        {
            visited[nextX][nextY] = 1;
            dfsGraph[nextX][nextY] = 2;
            dfs(nextX, nextY);
        }
    }
}

void checkWall(int x)
{
    if (x == 3)
    {

        for (int i = 0; i < N; i++)
        {
            for (int j = 0; j < M; j++)
            {
                dfsGraph[i][j] = tmpGraph[i][j];
                visited[i][j] = 0;
            }
        }

        for (int i = 0; i < N; i++)
        {
            for (int j = 0; j < M; j++)
            {
                if (dfsGraph[i][j] == 2 && !visited[i][j])
                {
                    visited[i][j] = 1;
                    dfs(i, j);
                }
            }
        }

        cnt = 0;
        for (int i = 0; i < N; i++)
        {
            for (int j = 0; j < M; j++)
            {
                if (dfsGraph[i][j] == 0)
                    cnt++;
            }
        }
        result = max(result, cnt);

        return;
    }

    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < M; j++)
        {
            if (tmpGraph[i][j] == 0)
            {
                tmpGraph[i][j] = 1;
                checkWall(x + 1);
                tmpGraph[i][j] = 0;
            }
        }
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> N >> M;
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < M; j++)
        {
            cin >> graph[i][j];
        }
    }
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < M; j++)
        {
            if (graph[i][j] == 0)
            {
                for (int k = 0; k < N; k++)
                {
                    for (int l = 0; l < M; l++)
                    {
                        tmpGraph[k][l] = graph[k][l];
                    }
                }
                tmpGraph[i][j] = 1;
                checkWall(1);
                tmpGraph[i][j] = 0;
            }
        }
    }
    cout << result;
}

 

먼저, https://jaimemin.tistory.com/search/14502

'14502'의 검색결과

이곳의 코드를 참고했다. 이 코드를 충분히 이해한 이후 내 나름대로 dfs 방식으로 풀어야겠다는 생각을 가졌고 결국 풀긴 했지만 시간이 꽤 걸렸다.....

 

parameter의 개수를 조금 늘려서 for loop 도는 횟수를 크게 줄일 수 있을 것 같긴한데 귀찮아서 그렇게까지는 하지 않았다. 이 코드에서 사용한 벽을 세우고 ----> 함수 호출 ----> 벽 제거 이 개념을 잘 기억해둘 필요가 있다.