[ 백준 2234 ] 성곽 (C++)

백준의 성곽(2234) 문제이다.

( 문제 바로가기 )

[ 문제풀이 ]

1. 문제를 보면 일단 입력이 상당히 마음에 안든다. 이상한 숫자들이 막 적혀있다. 읽어보면 대충 이런말이다.

   성에 방이 있는데(MAP에서 한칸을 의미) 그 방에는 벽이 존재한다. 따라서 벽이 존재하는 곳으로는 이동할 수 없고 벽이 없는

   곳으로만 이동할 수 있는데 그 벽이 있는 위치를 입력으로 숫자로 나타낸 것이다.

   서쪽 = 1 , 북쪽 = 2, 동쪽 = 4, 남쪽 = 8로 표시한다고 되어있는데, 이 말은...

   예를 들어 값이 1이라면, 해당 지점에서는 서쪽에만 벽이 있음을 의미한다.

   값이 3이라면, 3 = 1 + 2, 즉 서쪽과 북쪽에 있다는 것을 의미한다.

   예제 입력의 첫줄을 보면 11 6 11 6 3 10 6 으로 이루어져있는데 이 말의 의미는 (0,0)의 값은 11 = 8 + 2 + 1 = 남,북,서 쪽에

   벽이있다. (0, 1)의 값은 6 = 4 + 2 = 동쪽과 북쪽에 벽이 있다는 의미이다.

2. 이제 입력이 무슨 의미인지 알았으니 구하고자 하는 것을 구해보자.

   1. 이 성에 있는 방의 갯수

   2. 가장 넓은 방의 넓이

   3. 하나의 벽을 제거하여 얻을 수 있는 가장 넓은 방의크기

   이 3개를 구해야하는데... BFS를 사용한다면 3가지 모두 어렵지 않게 구할 수 있을 것이란 느낌이 든다.

   물론, BFS안에서 움직일 수 있는 조건을 잘 생각해줘야 한다.

   벽이 어디에 있는지 판단만 잘하고 움직일 때와 움직일 수 없을 때만 잘 구분지어 준다면, 3가지 값은 쉽게 구할 것이다.

  

3. 그렇다면 움직일 수 있는 조건에 대해서 알아보자. 알아볼 것도 없다. 벽이 없으면 된다. 그렇다면 벽이 있고 없고를

   어떻게 판단해야할까? 답은 & 연산을 이용하면 쉽게 구할 수 있다.

   그렇다면 먼저 일반적인 BFS에서를 한 점에서 상하좌우로 움직이는 코드에 대해서 보자.

  물론 수많은 문제들에 따라서 조건이 다르고 갈 수 있는 방향이 다르기 때문에 다르겠지

   만 가장 기본적이고 보편적인 방식을 적어본 것이다.(본인의 코드일 뿐입니다. 정답이 아닙니다.)

   이 문제에서는 저 4방향으로 탐색할 때 벽이 있는지 없는지를 같이 탐색해줘야 한다.

   탐색하는 방법은 어렵지 않다. 저 안에서 맵의 해당정점의 값과, [1, 2, 4, 8] 이 4개의 값에 대해서 &연산을 해보면 된다.

   예를들어 현재 정점의 값이 11 이라고 생각해보자.

   11 = 8 + 2 + 1 로 이루어져 있고, 이는 서, 북, 남쪽에 벽이 있다는 의미이다.

   위에서 말한 차례대로 & 연산을 해보자.

   11 & 1 = 1011 & 0001 = 0001

   11 & 2 = 1011 & 0010 = 0010

   11 & 4 = 1011 & 0100 = 0000

   11 & 8 = 1011 & 1000 = 1000

   보면 1,2,4,8을 순서대로 연산을 하면서 그 결과값이 &연산을 한값과 똑같이 나오면 벽이 있다는 의미이다.

   구체적으로 설명해보겠다. 먼저 서쪽벽을 의미하는 1과 연산 한 부분을 보자.

   1011 과 0001 을 연산하면 0001이 나오게된다. 즉 결과값이 서쪽벽을 의미하는 1이라는 값이 나오게 된다.

   이와 같은 논리에 의해서 서쪽, 남쪽, 북쪽 벽은 모두 그 벽이 의미하는 값이 나오게 되지만

   벽이 없는 동쪽벽은 보면 0000 이라는 동쪽벽을 의미하는 4라는 값이 나오지 않는다.

   이러한 방식을 통해서 벽의 여부를 판단할 수 있다.

   코드를 이렇게 구현한다면, 벽이 없는 곳에 대해서만 진행할 수 있을 것이다.

4. 이제 어려운 부분은 끝났다.  
   1. 이 성에 있는 방의 갯수

   2. 가장 넓은 방의 넓이

   3. 하나의 벽을 제거하여 얻을 수 있는 가장 넓은 방의크기

   이 3가지를 구하는 방법을 설명해보겠다.

   1번은 BFS를 호출하는 횟수가 될 것이다. 본인은 방문하지 않은 정점에 대해서만 BFS를 호출하였고, 이렇게 구현을 했다면

   BFS의 호출 횟수가 방의 갯수가 될 것이다. ( 잘 생각해보면 방의 갯수 = BFS호출횟수 라는 것을 알 수 있음 )

   2번은 BFS를 돌리면서 방의 갯수를 Count할 변수 하나만 두고, 방문할 수 있는 정점이라서 Q에 push될 때마다 그 변수값을

   ++시켜주는 연산을 해준다면 가장 넓은 방의 크기를 구할 수 있을 것이다.

   3번은 한번 더 생각해봐야 하는 부분이다. 존재하는 모든 벽을 하나씩 다 없애봐야 한다.

   벽을 없애는 방법도 어렵지 않다.

   위에서 말한대로 현재 정점의 값과 [1, 2, 4, 8] 4개의 값을 연산하면 벽이 어느방향에 있는지 판단할 수 있다고는 위에서 말했다.

   그렇다면 이제는 벽을 없애보자.

   11을 예로들면, [1, 2, 8] 이 3가지 값에 대해서는 1,2,8의 값이 그대로 나온다. 즉, 이 정점에서 없애 볼수 있는 벽이 있다는 의미이

   다. 없애는 것은 그 값을 빼주면된다.

   무슨 소린지 말하는 나도 모르겠다. 11에서 1을 빼줘보자. 그럼 10이라는 값이 되고 이는 8 + 2 로써 북쪽과 남쪽에만 벽이 있음

   을 의미하는 값이 된다. 즉, 해당 벽이 의미하는 값을 해당 정점이 가진 값에서 빼주면 그 벽을 없애는 것과 동일한 효과라는

   것이다.

   11에서 2를 빼면? 9가 되는데 이는 8 + 1이 되고, 이 값은 서쪽과 남쪽에만 벽이 있음을 의미하는 값이 된다.

   이렇게 해당정점의 값과 벽의 의미하는 값들인 [1, 2, 4, 8] 을 & 연산을 통해서 벽이 있는 곳이라면, 그 값을 빼주고

   BFS를 실행하게 되면, 그 벽을 제외했을 때의 BFS결과가 나오게 된다.

   물론, 어느 한 지점에서 벽을 없애고 진행해서 원하는 결과를 알았다면, 그 값을 다시 더해줌으로써 벽을 다시 생성해주는

   과정도 필요하다 !

[ 소스코드 ]

#include<iostream>
#include<queue>
#include<cstring>
 
#define endl "\n"
#define MAX 50
using namespace std;
 
int N, M;
int MAP[MAX][MAX];
bool Visit[MAX][MAX];
 
int dx[] = { 0, -1, 0, 1 };
int dy[] = { -1, 0, 1, 0 };
 
int Bigger(int A, int B) { if (A > B) return A; return B; }
 
void Input()
{
    cin >> M >> N;
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < M; j++)
        {
            cin >> MAP[i][j];
        }
    }
}
 
int BFS(int a, int b)
{
    int Room_Size = 0;
    queue<pair<int, int>> Q;
    Q.push(make_pair(a, b));
    Visit[a][b] = true;
    Room_Size++;
 
    while (Q.empty() == 0)
    {
        int x = Q.front().first;
        int y = Q.front().second;
        Q.pop();
 
        int Wall = 1;
 
        for (int i = 0; i < 4; i++)
        {
            if ((MAP[x][y] & Wall) != Wall)
            {
                int nx = x + dx[i];
                int ny = y + dy[i];
 
                if (nx >= 0 && ny >= 0 && nx < N && ny < M)
                {
                    if (Visit[nx][ny] == false)
                    {
                        Room_Size++;
                        Visit[nx][ny] = true;
                        Q.push(make_pair(nx, ny));
                    }
                }
            }
            Wall = Wall * 2;
        }
    }
    return Room_Size;
}
 
void Solution()
{
    int Room_Cnt = 0;
    int Biggest_Room_Size = 0;
 
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < M; j++)
        {
            if (Visit[i][j] == false)
            {
                Biggest_Room_Size = Bigger(Biggest_Room_Size, BFS(i,j));
                Room_Cnt++;
            }
        }
    }
 
    cout << Room_Cnt << endl;
    cout << Biggest_Room_Size << endl;
 
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < M; j++)
        {
            for (int Wall = 1; Wall <= 8; Wall *= 2)
            {
                if ((MAP[i][j] & Wall) == Wall)
                {
                    memset(Visit, false, sizeof(Visit));
                    MAP[i][j] = MAP[i][j] - Wall;
                    Biggest_Room_Size = Bigger(Biggest_Room_Size, BFS(i, j));
                    MAP[i][j] = MAP[i][j] + Wall;
                }
            }
        }
    }
 
    cout << Biggest_Room_Size << endl;
}
 
void Solve()
{
    Input();
    Solution();
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}