BOJ 2234 [성곽]

BOJ 성곽 : https://www.acmicpc.net/problem/2234

안녕하세요. 이번 문제는 백준 온라인 저지의 [성곽] 입니다.

우선 1, 2번 요구사항의 경우는, 기본적인 BFS문제입니다.

다만, 입력이 평소의 문제와 조금 다릅니다. 

우선, 이진법을 통해 각 위치의 동서남북을 1로 설정합니다.

여기서 MAP을 2배 늘려서 이동을 2칸씩 하고, 벽은 한칸 뒤에 놓았습니다.

다음 3번에서 사용한 방법입니다.

1. 먼저 BFS를 통해 구한 방의 size와 방 번호를 노드 배열형태로 저장.

2. for문을 돌면서, 인접 좌표의 방번호가 다르면, 해당 방의 size를 비교

모든 좌표를 돌면서, 상하좌우를 확인하고 방 번호가 다를 때,

방의 사이즈를 더한 값의 최대를 구하면, 벽을 뚫을 때의 최대값을 구할 수 있습니다.

#include <iostream>
#include <cmath>
#include <queue>
using namespace std;
int Map[102][102];
int d[4][2] = { {0, -1}, {-1, 0}, {0, 1}, {1, 0} };
int d2[4][2] = { {-2, 0}, {0, -2}, {2, 0}, {0, 2} };
int N, M;
bool Visited[102][102];
int res = 0;
queue<pair<int, int>> q;
queue<pair<int, int>> q2;
int depth = 0;
class Node {
public:
    int room_num, size;
    Node() { };
};
Node info[102][102];
int BFS() {
    int result = 0;
        while(!q.empty()) {
            int i = q.front().first;
            int j = q.front().second;
            q2.push(make_pair(i, j));
            q.pop();
            result++;
            for(int k = 0; k < 4; k++) {
                if(Map[i + d[k][0]][j + d[k][1]] == 0) {
                    int next_i = i + 2*d[k][0];
                    int next_j = j + 2*d[k][1];
                    if(next_i >=1 && next_i < 2*N && next_j >= 1 && next_j < 2*M) {
                        if(!Visited[next_i][next_j]) {
                            Visited[next_i][next_j] = true;
                            q.push(make_pair(next_i, next_j));
                        }
                    }
                }
            }
        
    }
    return result;
}
int main() {
    cin >> M >> N;
    for(int i = 0; i < N; i++) {
        for(int j = 0; j < M; j++) {
            int num;
            cin >> num;
            for(int k = 3 ; k >= 0; k--) {
                if(num >= pow(2, k)) {
                    Map[1 + i*2 + d[k][0]][1 + j*2 + d[k][1]] = 1;
                    num -= pow(2,k);
                }
            }
        }
    }
    int cnt = 0;
    int Largest = 0;
    int crushed = 0;
    for(int i = 0; i < N; i++) {
        for(int j = 0; j < M; j++) {
            if(!Visited[1 + 2*i][1 + 2*j]) {
                Visited[1 + 2*i][1 + 2*j] = true;
                cnt++;
                q.push(make_pair(1 + 2*i, 1 + 2*j));
                int temp = BFS();
                Largest = Largest > temp ? Largest : temp;
                while(!q2.empty()) {
                    int node_i = q2.front().first;
                    int node_j = q2.front().second;
                    info[node_i][node_j].size = temp;
                    info[node_i][node_j].room_num = depth;
                    q2.pop();
                }
                depth++;
            }
        }
    }
    for(int i = 0; i < N; i++) {
        for(int j = 0; j < M; j++) {
            int ori_i = 1 + 2*i;
            int ori_j = 1 + 2*j;
            for(int k = 0; k <4; k++) {
                int diff_i = ori_i + d2[k][0];
                int diff_j = ori_j + d2[k][1];
                if(diff_i >= 1 && diff_i < 2*N && diff_j >= 1 && diff_j < 2*N) {
                    if(info[ori_i][ori_j].room_num != info[diff_i][diff_j].room_num) {
                        crushed = info[ori_i][ori_j].size + info[diff_i][diff_j].size > crushed ? info[ori_i][ori_j].size + info[diff_i][diff_j].size : crushed;
                    }
                }
            }
        }
    }
    cout << cnt << endl;
    cout << Largest << endl;
    cout << crushed << endl;
    return 0;
}