[ 백준 ] 2234 / 성곽

金弘均·2021년 9월 16일
0

Baekjoon Online Judge

목록 보기
164/228
post-thumbnail
post-custom-banner

# Appreciation

/*
 * Problem :: 2234 / 성곽
 *
 * Kind :: BFS
 *
 * Insight
 * - 벽을 어떻게 다루면 좋을까...?
 *   + 3차원으로 생각하자!
 *    # 서쪽=0, 북쪽=1, 동쪽=2, 남쪽=3 이라고 하면,
 *      (i,j) 좌표의 북쪽에 벽이 있을 경우
 *      (bool) isWall[i][j][1] = true 로 다룰 수 있다
 *
 * - 벽을 다루는 것 외에는 전형적인 DFS, BFS 문제
 *   + 다만, 3의 답(하나의 벽을 제거하여 얻을 수 있는 가장 넓은 방의 크기) 의 경우,
 *     이를 계산하기 위해서 DFS, BFS 를 매 칸마다 다시 도는 것은 비효율적이다
 *     # 한번 DFS 또는 BFS 돌때 각 칸을 라벨링(labeling) 해주자
 *       -> 같은 방이면 같은 라벨을 가지게끔 하고
 *          그 라벨에 해당하는 방의 개수를 저장해두면
 *          인접한 칸을 조사해보는 것만으로도 3의 답을 알 수 있다!
 *          (같은 라벨이면 같은 방, 다른 라벨이면 다른 방)
 *
 * Point
 * - 벽의 유무를 확인할 때
 *   문제의 설명대로 비트연산을 활용하자
 *   
 * - 방의 넓이를 구하는 데는 DFS 보다 BFS 가 나을 것 같아서
 *   BFS 를 사용하였다
 */

# Code

//
//  BOJ
//  ver.C++
//
//  Created by GGlifer
//
//  Open Source

#include <iostream>
#include <map>
#include <queue>

using namespace std;

#define endl '\n'

// Set up : Global Variables
int M, N;
bool isWall[50][50][4];
bool isVisited[50][50];
int label[50][50];
map<int,int> S;
int dy[4] = {0, -1, 0, +1}; /* 서쪽=0, 북쪽=1, 동쪽=2, 남쪽=3 */
int dx[4] = {-1, 0, +1, 0};
struct Point { int y, x; };

// Set up : Functions Declaration
bool isValid(int y, int x);
int bfs(int sy, int sx, int no);


int main()
{
    // Set up : I/O
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    // Set up : Input
    cin >> N >> M;
    for (int i=0; i<M; i++) {
        for (int j=0; j<N; j++) {
            int val; cin >> val;
            for (int k=0; k<4; k++) {
                if (val & (1<<k)) { /* 비트 연산을 활용하여 벽의 유무 판별 */
                    isWall[i][j][k] = true;
                }
            }
        }
    }

    // Process
    int ans1 = 0, ans2 = -1; /* ans1 = 방의 개수, ans2 = 가장 넓은 방의 넓이 */
    for (int i=0; i<M; i++) {
        for (int j=0; j<N; j++) {
            if (not(isVisited[i][j])) { /* 방문하지 않은 칸을 만나면 */
                ans1++; /* 방의 개수 증가 */
                int size = bfs(i, j, ans1); /* BFS 로 방의 넓이 구함 */
                S[ans1]= size; /* 방의 개수를 라벨로 하여 방의 넓이를 저장 */
                ans2 = max(ans2, size); /* 가장 넓은 방의 넓이 갱신 */
            }
        }
    }

    int ans3 = -1; /* ans3 = 하나의 벽을 제거하여 얻을 수 있는 가장 넓은 방의 크기 */
    for (int i=0; i<M; i++) {
        for (int j=0; j<N; j++) { /* (i,j) 에서 */
            for (int k=0; k<4; k++) { /* 차례로 서쪽, 북쪽, 동쪽, 남쪽에 벽이 있다면 */
                if (isWall[i][j][k]) {
                    int ay = i + dy[k]; /* 그 방향으로 인접한 칸의 좌표를 구함 */
                    int ax = j + dx[k];
                    if (isValid(ay, ax)) { /* 유효하면 */
                        int l1 = label[i][j]; /* 현재 칸의 라벨 */
                        int l2 = label[ay][ax]; /* 인접한 칸의 라벨 */
                        if (l1 != l2) { /* 같은 방이 아니면 */
                            ans3 = max(ans3, S[l1]+S[l2]);
                        }
                    }
                }
            }
        }
    }

    // Control : Output
    cout << ans1 << endl;
    cout << ans2 << endl;
    cout << ans3 << endl;
}

// Helper Functions
bool isValid(int y, int x)
/* 좌표 (y,x) 가 유효하면 true 를 반환, 그 외 false 를 반환 */
{
    return y >= 0 && y < M && x >= 0 && x < N;
}

int bfs(int sy, int sx, int no)
/* 좌표 (sy,sx) 가 포함된 방의 넓이를 반환
 * 그 방에 포함된 좌표들은 no 로 라벨링 됨 */
{
    queue<Point> que;
    que.push({sy, sx});
    isVisited[sy][sx] = true;

    int size = 0; /* 방의 넓이 */

    while (not(que.empty())) {
        int cy = que.front().y;
        int cx = que.front().x;
        que.pop();

        size++; /* 방의 넓이 증가 */
        label[cy][cx] = no; /* 라벨링 */

        for (int i=0; i<4; i++) {
            int ny = cy + dy[i];
            int nx = cx + dx[i];
            /* 좌표 (ny,nx) 가 유효하고 방문된 적이 없으며 사이에 벽이 없다면 */
            if (isValid(ny, nx) && not(isVisited[ny][nx]) && not(isWall[cy][cx][i])) {
                /* 방문 처리 */
                isVisited[ny][nx] = true;
                que.push({ny, nx});
            }
        }
    }

    return size;
}
profile
이런 미친 게임을 봤나! - 옥냥이
post-custom-banner

0개의 댓글