[백준] 2234 성곽

2234번: 성곽

 

www.acmicpc.net

풀이

상당히 구현할게 많고 까다로운 문제였다. BFS를 사용해서 방을 분리하고, BFS를 한번 더 사용해서 각 방들끼리의 관계를 인접 리스트로 표현했다. 벽을 한개만 부셔도 2개의 방은 합쳐질 수 있으므로 서로 인접해 있는 방 2개의 합이 가장 큰 경우를 찾아주었다.

코드

#include <iostream>
#include <vector>
#include <queue>
#include <set>
#include <algorithm>
using namespace std;

int m, n;
bool can_left, can_up, can_right, can_down;
int map[51][51];
int area[51][51];
bool chk[51][51];
vector<int> v;
vector<set<int>> adj;
const int dx[] = { -1, 0, 1, 0 }, dy[] = { 0, -1, 0, 1 };

// 상하좌우로 이동할 수 있는지 확인해주는 함수
void can_move(int x, int y) {
    can_left = false; can_up = false; can_right = false; can_down = false;
    can_left = !(map[y][x] & 1);
    can_up = !(map[y][x] & 2);
    can_right = !(map[y][x] & 4);
    can_down = !(map[y][x] & 8);
}

// 방을 나누기 위한 함수. 방의 크기를 계산하여 리턴
int bfs(int x, int y, int idx) {
    int ret = 1;
    queue<pair<int, int>> q;
    area[y][x] = idx;
    q.push({ x, y });

    while (!q.empty()) {
        int x = q.front().first;
        int y = q.front().second;
        q.pop();

        // 상하좌우 이동할 수 있는지 확인
        can_move(x, y);

        // 왼쪽으로 이동가능한 경우
        if (can_left && !area[y][x - 1]) {
            area[y][x - 1] = idx;
            q.push({ x - 1, y });
            ret++;
        }

        // 위쪽으로 이동가능한 경우
        if (can_up && !area[y - 1][x]) {
            area[y - 1][x] = idx;
            q.push({ x, y - 1 });
            ret++;
        }

        // 오른쪽으로 이동가능한 경우
        if (can_right && !area[y][x + 1]) {
            area[y][x + 1] = idx;
            q.push({ x + 1, y });
            ret++;
        }

        // 아래쪽으로 이동가능한 경우
        if (can_down && !area[y + 1][x]) {
            area[y + 1][x] = idx;
            q.push({ x, y + 1 });
            ret++;
        }
    }
    return ret;
}

// 인접리스트를 생성해주는 함수
void make_adj(int x, int y) {
    queue<pair<int, int>> q;
    q.push({ x, y });
    chk[y][x] = true;
    int idx = area[y][x];

    while (!q.empty()) {
        int x = q.front().first;
        int y = q.front().second;
        q.pop();

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

            // 성곽을 벗어나는 경우
            if (nx < 0 || nx > n || ny < 0 || ny > m) continue;
            // 같은 방이면서 아직 방문하지 않은 경우
            if (area[ny][nx] == idx && !chk[ny][nx]) {
                q.push({ nx, ny });
                chk[ny][nx] = true;
            }
            // 인접한 방을 발견한 경우 (방의 번호는 1번부터 시작하므로 방의 번호가 0번인 경우는 제외하였다)
            else if(area[ny][nx] != 0 && area[ny][nx] != idx) adj[idx].insert(area[ny][nx]);
        }
    }
}

int main() {
    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 >> map[i][j];

    int idx = 1;
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (area[i][j]) continue;
            int tmp = bfs(j, i, idx++);
            v.push_back(tmp);
        }
    }
    adj = vector<set<int>>(v.size() + 1);

    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (chk[i][j]) continue;
            make_adj(j, i);
        }
    }

    int ans = 0;
    for (int i = 1; i < adj.size(); i++) {
        for (auto it = adj[i].begin(); it != adj[i].end(); it++) {
            ans = max(ans, v[i-1] + v[(*it) - 1]);
        }
    }
    cout << v.size() << '\n' << *max_element(v.begin(), v.end()) << '\n' << ans << '\n';
    return 0;
}