2234 성곽

#include <iostream>
#include <queue>
#include <algorithm>
#include <cstring>

using namespace std;

typedef struct
{
    int m;
    int n;
} dot;

int m, n; // m: row, n: column
int graph[50][50] = {0, };
bool check[50][50] = {false, };

// west, north, east, south
int dm[] = {0, -1, 0, 1};
int dn[] = {-1, 0, 1, 0};

int roomNum;
int room[2501] = {0, }; // room[roomNum] = roomSize

int bfs(dot start)
{
    queue<dot> q;
    q.push(start);
    check[start.m][start.n] = true;
    int roomSize = 1;

    while (!q.empty()) {
        dot next = q.front();
        q.pop();

        int bit = 1;
        for (int i = 0; i < 4; i++) {
            if (!(bit & graph[next.m][next.n])) {
                int nextm = next.m + dm[i];
                int nextn = next.n + dn[i];
                if (!(nextm >= 0 && nextm < m && nextn >= 0 && nextn < n)) { 
                    continue;
                }
                if (check[nextm][nextn] == false) {
                    q.push({nextm, nextn});
                    check[nextm][nextn] = true;
                    roomSize++;
                }
            }
            bit <<= 1;
        }        
    }

    return roomSize;
}

void solve()
{
    int bigRoomSize = 0;

    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (check[i][j] == false) {             
                room[roomNum++] = bfs({i, j});
            }
        }
    }

    for (int i = 0; i < roomNum; i++) {
        if (room[i] > bigRoomSize) {
            bigRoomSize = room[i];
        }
    }

    cout << roomNum << endl;
    cout << bigRoomSize << endl;
    
    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) == k) {
                    memset(check, false, sizeof(check));
                    graph[i][j] -= k;
                    bigRoomSize = max(bigRoomSize, bfs({i, j}));
                    graph[i][j] += k;
                }
            }
        }
    }

    cout << bigRoomSize << endl;
}

void input()
{
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            cin >> graph[i][j];
        }
    }
}

int main(void)
{
    input();
    solve();

    return 0;
}

푸는데 정말 오랜 시간이 걸린 문제다.

우선 벽이 숫자로 주어졌을때 어느 방향으로 움직일 수 있는지 결정해야 했다.

몇번 삽질을 반복한 결과 벽을 의미하는 숫자를 1을 왼쪽으로 쉬프트 하면서 연산하니 해결했다.

그렇게 1번, 2번의 답은 해결했지만 3번 답을 해결하는게 제일 어려웠다.

질문 검색 해가면서 여차여차 답은 얻었지만 완전히 이해한게 아니라 좀 찝찝하다.

다시 한번 살펴봐야겠다.