[백준] 2234번
2234 성곽
문제
대략 위의 그림과 같이 생긴 성곽이 있다. 굵은 선은 벽을 나타내고, 점선은 벽이 없어서 지나다닐 수 있는 통로를 나타낸다. 이러한 형태의 성의 지도를 입력받아서 다음을 계산하는 프로그램을 작성하시오.
- 이 성에 있는 방의 개수
- 가장 넓은 방의 넓이
- 하나의 벽을 제거하여 얻을 수 있는 가장 넓은 방의 크기
위의 예에서는 방은 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을 더한 값이 주어진다고 하였으니 각 칸을 방문할때마다 벽이 있는지 없는지를 확인해줬다.
1 2 3 4 5 6 7 8 9 | 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; //벽이 있음을 표시 } } | cs |
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을 통해 하나의 방에 연결된 다른 방들과의 관계를 알아보고,
만약 다른 어떤 방과 연결되었을 때의 넓이들을 구해 벽의 제거시에 합친 방의 최대 넓이를 찾으면 된다.
코드)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 | #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; } | cs |
결과)
(추가)
채점현황을 보니, 메모리는 다른 사람에 비해 적게 사용하나 시간이 100ms정도 차이가 났다.
그래서 다른 분들을 어떻게 풀었나 살펴보니
나처럼 set을 통해 연결관계를 만들지 않고, bfs를 2번 사용했을음 알았다.
1. 방 번호 찾고, 각 방의 넓이를 구하는 bfs
2. 각 방의 시작점을 저장해둔 걸 이용하여, 방과 방사이에 연결을 구하는 bfs