백준 2234번 성곽

문제 링크입니다: https://www.acmicpc.net/problem/2234

BFS(Breadth First Search) 알고리즘과 비트마스킹을 이용하여 풀어야했던 문제였습니다.

알고리즘은 아래와 같습니다.

1. 성곽을 순회하면서 아직 방문하지 않은 지점을 기점으로 BFS 함수를 호출합니다.

->DFS 알고리즘을 이용하여 컴포넌트 개수를 찾듯이 BFS 함수를 호출합니다.

2. BFS 함수는 해당 인덱스와 비트를 이용하여 해당 지점으로 갈 수 있는지를 확인하고 갈 수 있다면 방문했다고 표시한 후 큐에 넣습니다.

3. 1번과 2번을 통해 첫 번째 답과 두 번째 답을 얻을 수 있습니다.

4. 세 번째 답을 구하기 위해서는 벽을 하나하나 허물어봐야합니다.

i) 따라서, 각 인덱스의 벽을 비트 연산을 통해 허뭅니다.

ii) i)에서 허문 상태로 BFS 함수를 호출합니다.

iii) i)과 ii)를 통해 얻은 최대값을 출력해줍니다.

#include <iostream>

#include <queue>

#include <algorithm>

using namespace std;

 

const int MAX = 50;

 

typedef struct

{

        int y, x;

}Dir;

 

Dir moveDir[4] = { {0, -1}, {-1, 0}, {0, 1}, {1, 0} };

 

int N, M;

int area;

int graph[MAX][MAX];

bool visited[MAX][MAX];

 

int BFS(int y, int x)

{

        queue<pair<int, int>> q;

        q.push({ y, x });

        visited[y][x] = true;

        int cnt = 1;

 

        while (!q.empty())

        {

                 int curY = q.front().first;

                 int curX = q.front().second;

                 q.pop();

 

                 int bit = 1;

                 //서,북,동,남 벽 확인

                 for (int i = 0; i < 4; i++)

                 {

                         if (!(graph[curY][curX] & bit))

                         {

                                 int nextY = curY + moveDir[i].y;

                                 int nextX = curX + moveDir[i].x;

                                 //부시면 안되는 벽 부셨을 경우

                                 if (!(0 <= nextY && nextY < M && 0 <= nextX && nextX < N))

                                          continue;

                                

                                 //방문하지 않은 곳

                                 if (!visited[nextY][nextX]) {

                                          cnt++;

                                          visited[nextY][nextX] = true;

                                          q.push({ nextY, nextX });

                                 }

                         }

                         bit <<= 1;

                 }

        }

        return cnt;

}

 

int main(void)

{

        ios_base::sync_with_stdio(0);

        cin.tie(0);

        cin >> N >> M;

 

        for (int i = 0; i < M; i++)

                 for (int j = 0; j < N; j++)

                         cin >> graph[i][j];

 

        int cnt = 0;

        for(int i=0; i<M; i++)

                 for(int j=0; j<N; j++)

                         if (!visited[i][j])

                         {

                                 area = max(area, BFS(i, j));

                                 cnt++;

                         }

 

        cout << cnt << "\n";

        cout << area << "\n";

        //벽을 없애보자

        for(int i=0; i<M; i++)

                 for(int j=0; j<N; j++)

                         for (int k = 1; k <= 8; k <<= 1)

                                 if (graph[i][j] & k)

                                 {

                                          memset(visited, false, sizeof(visited));

                                          graph[i][j] -= k;

                                          area = max(area, BFS(i, j));

                                          graph[i][j] += k;

                                 }

 

        cout << area << "\n";

        return 0;

}

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~