[C++] 백준 2234번: 성곽

문제

난이도 : 골드 3
백준 2234번 : 성곽

코드

#include <bits/stdc++.h>

using namespace std;

int M, N;
int arr[54][54];
int visited[54][54];

int dy[] = { 0, -1, 0, 1 };
int dx[] = { -1, 0, 1, 0 };

int answer1, answer2, answer3;
int room;

void DFS(int y, int x)
{
    room++;
    visited[y][x] = 1;

    for (int i = 0; i < 4; i++)
    {
        int ny = y + dy[i];
        int nx = x + dx[i];

        if (ny < 0 || nx < 0 || ny >= M || nx >= N) continue;
        if (arr[y][x] & (1 << i) || visited[ny][nx]) continue;

        DFS(ny, nx);
    }

}

int main()
{
    cin >> N >> M;

    for (int i = 0; i < M; i++)
    {
        for (int j = 0; j < N; j++)
        {
            cin >> arr[i][j];
        }
    }

    for (int i = 0; i < M; i++)
    {
        for (int j = 0; j < N; j++)
        {
            if (visited[i][j]) continue;
            room = 0;
            DFS(i, j); answer1++;
            answer2 = max(answer2, room);
        }
    }
    

    for (int i = 0; i < M; i++)
    {
        for (int j = 0; j < N; j++)
        {
            for (int k = 0; k < 4; k++)
            {
                memset(visited, 0, sizeof(visited));

                if (arr[i][j] & (1 << k))
                {
                    arr[i][j] &= ~(1 << k);
                    room = 0;
                    DFS(i, j);
                    answer3 = max(answer3, room);
                    arr[i][j] |= (1 << k);
                }
            }
        }
    }

    cout << answer1 << '\n' << answer2 << '\n' << answer3;

    return 0;
}

설명

그래프와 비트마스킹을 이용해 푸는 문제
최단거리를 구할 필요가 없으니 DFS를 사용했다. 각 방에 어떻게 벽이 있는지 정보를 입력받은 뒤 각 방을 반복문을 돌며 방문한 곳이 아니라면 DFS를 실행함
일반적인 DFS와는 다르게 서쪽, 북쪽, 동쪽, 남쪽으로 방향벡터를 구성했는데 방의 0번째 인덱스가 서쪽, 1번째가 북쪽, … , 3번째가 남쪽 벽의 존재 유무를 가리키기때문
그래서 if(arr[y][x] & (1 « i))를 이용해 만약 동쪽으로 가려고 하는데 동쪽 방향에 벽이 있다면 0100 & 0100 = 0100이 되어 true가 되니 그쪽으로는 못간다는 뜻이 된다
그렇게 해서 방의 개수와 가장 넓은 방의 넓이를 구한다음 이제 방마다 벽을 무너뜨리는 방법을 생각해보자
비슷하게 for문을 돌건데 안쪽 루프에 네 방향으로 벽이 있는지 확인하고 무너뜨리고 DFS를 돌아 방의 넓이를 구한 후 복구하는 로직을 넣었다
입력이 크지 않아 충분히 검사가 가능했고 정답도 제대로 나오는 것을 볼 수 있었다

결과