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

https://www.acmicpc.net/problem/2234

 

 

이 문제는 격자판이 주어지고 격자판 요소를 2진수로 나타냈을때 각 자리 숫자가 1일 경우 비트 수에 따라서 방향에 벽이 있다는 것이며 0일 경우 벽이 없으며 격자판에 대한 정보를 가지고 1, 2, 3번에 대한 결과를 출력하는 문제이다.

 

먼저 1, 2, 3번 문제를 살펴보면

 

1. 이 성에 있는 방의 개수 -> 격자를 살펴보며 방문하지 않은 칸에 bfs를 호출하여 cnt를 증가시킨다 이때 cnt값이 방의 개수이다.

2. 가장 넓은 방의 넓이 -> 1번에서 bfs함수를 호출할때 요소들의 개수도 더해주어 배열에 넓이를 넣어준다. ex) arr[cnt] = 넓이

3. 하나의 벽을 제거하여 얻을 수 있는 가장 넓은 방의 크기 -> 1번에서 bfs를 호출했을때 각 지점들을 하나의 새로운 배열로 만들어 인덱스화 해준다. 즉 cnt가 1일 경우 새로운 배열에 방문했던 곳을 다 1로 만들어 하나의 방을 만들어 준다.

이때 각 격자에서 상하좌우를 살펴보며 요소 값이 다를 때 벽을 없애고 합친다는 의미이므로 arr배열에서 합하여 최댓값을 update 해준다.

 

 

정답코드

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
#define endl "\n"
#define MAX 1e9

struct coordinate {
    int x;
    string s;
    vector<int> v;
};

int dx[] = {0, -1, 0, 1, 1, -1, -1, 1};
int dy[] = {-1, 0, 1, 0, -1, 1, -1, 1};
int N, M;
int graph[51][51];
int arr[2501];
int dp[51][51];
int cnt = 1;

/*
    1. 방의 개수 -> set사용
    2. 가장 넓은 방의 넓이  -> 크기만큼 리턴
    3. 
*/

void bfs(int a, int b) {
    queue<pii> q;
    q.push({a, b});
    dp[a][b] = cnt;
    int count = 1;

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

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

                if(nx >= 0 && nx < M && ny >= 0 && ny < N) {
                    if(!dp[nx][ny]) {
                        dp[nx][ny] = cnt;
                        q.push({nx, ny});
                        count++;
                    }
                }
            }
        }
    }
    arr[cnt] = count;
}

void solve() {

    for(int i = 0; i < M; i++) {
        for(int j = 0; j < N; j++) {
            if(dp[i][j] == 0) {
                bfs(i, j);
                cnt++;
            }
        }
    }

    int answer3 = 0;

    for(int i = 0; i < M; i++) {
        for(int j = 0; j < N; j++) {
            for(int k = 0; k < 4; k++) {
                set<int> st;
                st.insert(dp[i][j]);
                int nx = i + dx[k];
                int ny = j + dy[k];

                if(nx >= M || nx < 0 || ny >= N || ny < 0) continue;

                if(dp[i][j] != dp[nx][ny]) {
                    int tmpsz = arr[dp[i][j]] + arr[dp[nx][ny]];
                    answer3 = max(answer3, tmpsz);
                }
            }
        }
    }

    int answer2 = 0;

    for(int i = 1; i < cnt; i++) {
        answer2 = max(answer2, arr[i]);
    }

    cout << cnt-1 << endl << answer2 << endl << answer3 << 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() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    input();
    solve();
}