[백준] 2234번

2234 성곽

문제

---

대략 위의 그림과 같이 생긴 성곽이 있다. 굵은 선은 벽을 나타내고, 점선은 벽이 없어서 지나다닐 수 있는 통로를 나타낸다. 이러한 형태의 성의 지도를 입력받아서 다음을 계산하는 프로그램을 작성하시오.

1. 이 성에 있는 방의 개수
2. 가장 넓은 방의 넓이
3. 하나의 벽을 제거하여 얻을 수 있는 가장 넓은 방의 크기

위의 예에서는 방은 5개고, 가장 큰 방은 9개의 칸으로 이루어져 있으며, 위의 그림에서 화살표가 가리키는 벽을 제거하면 16인 크기의 방을 얻을 수 있다.

성은 m×n(1 ≤ m, n ≤ 50)개의 정사각형 칸으로 이루어진다. 성에는 최소 두 개의 방이 있어서, 항상 하나의 벽을 제거하여 두 방을 합치는 경우가 있다.

입력

---

첫째 줄에 두 정수 n, m이 주어진다. 다음 m개의 줄에는 n개의 정수로 벽에 대한 정보가 주어진다. 벽에 대한 정보는 한 정수로 주어지는데, 서쪽에 벽이 있을 때는 1을, 북쪽에 벽이 있을 때는 2를, 동쪽에 벽이 있을 때는 4를, 남쪽에 벽이 있을 때는 8을 더한 값이 주어진다. 참고로 이진수의 각 비트를 생각하면 쉽다. 따라서 이 값은 0부터 15까지의 범위 안에 있다.

출력

---

첫째 줄에 1의 답을, 둘째 줄에 2의 답을, 셋째 줄에 3의 답을 출력한다.

---

풀이)

처음에는 bfs와 set을 사용해서 푼 문제이다.

bfs를 통해 각 칸이 어떤 방인지, 방의 크기는 얼마나 되는지 알아보았다. → 이 성에 있는 방의 개수와 가장 넓은 방의 넓이 구할수 있음

set을 통해 각 방들이 어떻게 연결되어 있는지 알아보았다. → 하나의 벽을 제거하여 얻을 수 있는 가장 넓은 방의 넓이 구할 수있음

자세히 살펴보자.

bfs를 할 때 

서쪽에 벽이 있을 때는 1을, 북쪽에 벽이 있을 때는 2를, 동쪽에 벽이 있을 때는 4를, 남쪽에 벽이 있을 때는 8을 더한 값이 주어진다고 하였으니 각 칸을 방문할때마다 벽이 있는지 없는지를 확인해줬다.

bool wall[4];//서북동남
fill(wall, wall + 4, false);
int temp = arr[y][x];
for (int i = 3; i >= 0; i--) {//남쪽부터 벽이 있는지 없는지 확인
    if (temp >= pow(2, i)) {
        temp -= pow(2, i);
        wall[i] = true; //벽이 있음을 표시
    }
}

1. 벽이 없을 시 : 같은 방이라는 얘기이므로 그 방의 넓이를 1씩 증가시켜준다.

2. 벽이 있을 시 : 다른 방이라는 얘기이므로 지금 현재의 방과 그 다른 방 사이가 연결되있음 set을 통해 표시해준다.

그림을 통해 보자면

예시로 주어진 그림에서, 방의 번호를 칸에다 지정했을시 int visited[][]함수에 이렇게 방번호로 저장되게 해두었다.

1	1	2	2	3	3	3
1	1	1	2	3	4	3
1	1	1	5	3	5	3
1	5	5	5	5	5	3

보라색 부분을 봤을때, 보라색칸은 2번방이다.

근데, 3번방과 연관관계가 있으므로 set에다가 {2,3} 라고 저장해두어 2번방과 3번방은 연결되어있음을 표시한다.

노란색 부분을 보자. 노란색 칸은 5번방이다.

5번방은 1, 2, 3번방과 만나고 있으므로 set에다가 {5,1},{5,2},{5,3}이라고 저장해둔다.

이렇게 set을 통해 각 방들이 어떻게 연결되었는지 알 수 있다.

즉, set을 통해 하나의 방에 연결된 다른 방들과의 관계를 알아보고,

만약 다른 어떤 방과 연결되었을 때의 넓이들을 구해 벽의 제거시에 합친 방의 최대 넓이를 찾으면 된다. 

코드)

#include <stdio.h>
#include <queue>
#include <algorithm>
#include <vector>
#include <math.h>
#include <set>
using namespace std;
 
int n, m;
int visited[50][50];
int arr[50][50];
//서북동남
int dy[4] = { 0,-1,0,1 };
int dx[4] = { -1,0,1,0 };
int room = 0; //방의 개수
int mrom;//가장 넓은 방의 넓이
int wrom;//벽을 없애고 넓은 방의 넓이
vector<int> coroom; //각 방들의 넓이
bool connect[52][52];
 
 
void bfs(int a, int b) {
    queue<pair<int, int>> qu;
    qu.push({ a,b });
    visited[a][b] = room;
    int c = 1;//현재 시작하는 방개수 포함
 
    while (!qu.empty())
    {
        int y = qu.front().first;
        int x = qu.front().second;
        qu.pop();
 
        bool wall[4];//서북동남
        fill(wall, wall + 4, false);
        int temp = arr[y][x];
        for (int i = 3; i >= 0; i--) {//남쪽부터 벽이 있는지 없는지 확인
            if (temp >= pow(2, i)) {
                temp -= pow(2, i);
                wall[i] = true; //벽이 있음을 표시
            }
        }
 
        for (int i = 0; i < 4; i++) {
            int ny = y + dy[i];
            int nx = x + dx[i];
 
            if (ny >= 0 && ny < m && nx >= 0 && nx < n) {
                
                if (visited[ny][nx] != 0) { //방문한적이 있을시
                    //같은 방이 아닌데 연결되있음이 표시 안되어있으면
                    if ((visited[ny][nx] != visited[y][x]) && connect[visited[y][x]][visited[ny][nx]] == false) {
                        connect[visited[y][x]][visited[ny][nx]] = true;
                    }
                    continue;
                }
                if (wall[i] == true) continue; //벽이 있는 방향이면, 같은 방이 아니라는 거니깐 탐색x
                c += 1;
                qu.push({ ny,nx });
                visited[ny][nx] = room;
            }
        }
    }
    mrom = max(mrom, c); //가장 넓은 방의 넓이 갱신
    coroom.push_back(c); //방의 넓이 저장
}
 
int main() {
    scanf("%d %d", &n, &m);
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            scanf("%d", &arr[i][j]);
        }
    }
 
    coroom.push_back(0);
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (visited[i][j] == 0) { //방문을 안한 칸일시
                room++;
                bfs(i, j);
            }
        }
    }
    wrom = mrom; //일단 가장 넓은 방의 넓이로 초기화해두고
 
    for (int i = 1; i <= room; i++) {
        for (int j = 1; j <= room; j++) {
            if (i == j)continue;
            if (connect[i][j]) {
                wrom = max(wrom, coroom[i] + coroom[j]);
            }
        }
    }
    printf("%d\n%d\n%d", room, mrom, wrom);
 
    return 0;
}

결과)

(추가) 

채점현황을 보니, 메모리는 다른 사람에 비해 적게 사용하나 시간이 100ms정도 차이가 났다.

그래서 다른 분들을 어떻게 풀었나 살펴보니

나처럼 set을 통해 연결관계를 만들지 않고, bfs를 2번 사용했을음 알았다.

1. 방 번호 찾고, 각 방의 넓이를 구하는 bfs

2. 각 방의 시작점을 저장해둔 걸 이용하여, 방과 방사이에 연결을 구하는 bfs