문제
대략 위의 그림과 같이 생긴 성곽이 있다. 굵은 선은 벽을 나타내고, 점선은 벽이 없어서 지나다닐 수 있는 통로를 나타낸다. 이러한 형태의 성의 지도를 입력받아서 다음을 계산하는 프로그램을 작성하시오.
- 이 성에 있는 방의 개수
- 가장 넓은 방의 넓이
- 하나의 벽을 제거하여 얻을 수 있는 가장 넓은 방의 크기
위의 예에서는 방은 5개고, 가장 큰 방은 9개의 칸으로 이루어져 있으며, 위의 그림에서 화살표가 가리키는 벽을 제거하면 16인 크기의 방을 얻을 수 있다.
성은 m×n(1 ≤ m, n ≤ 50)개의 정사각형 칸으로 이루어진다. 성에는 최소 두 개의 방이 있어서, 항상 하나의 벽을 제거하여 두 방을 합치는 경우가 있다.
입력
첫째 줄에 두 정수 n, m이 주어진다. 다음 m개의 줄에는 n개의 정수로 벽에 대한 정보가 주어진다. 벽에 대한 정보는 한 정수로 주어지는데, 서쪽에 벽이 있을 때는 1을, 북쪽에 벽이 있을 때는 2를, 동쪽에 벽이 있을 때는 4를, 남쪽에 벽이 있을 때는 8을 더한 값이 주어진다. 참고로 이진수의 각 비트를 생각하면 쉽다. 따라서 이 값은 0부터 15까지의 범위 안에 있다.
출력
첫째 줄에 1의 답을, 둘째 줄에 2의 답을, 셋째 줄에 3의 답을 출력한다.
예제 입력 1 복사
7 4 11 6 11 6 3 10 6 7 9 6 13 5 15 5 1 10 12 7 13 7 5 13 11 10 8 10 12 13
예제 출력 1 복사
5 9 16
단언코 백준에 있는 bfs 문제중에 매우매우 까다롭고 풀기 힘든 문제였다.
그만큼 풀고나면 뿌듯하다. 힘을내서 풀어보자.
일단 문제 입력부터 평범한 bfs 문제와 다르게 매우 지저분하다.
각 값을 2진수로 바꿔서 벽의 정보를 알 수 있다고 한다. 1은 서쪽 벽, 2는 북쪽, 4는 동쪽, 8은 남쪽 벽이라고 한다.
나는 binary[4] 배열을 통해 각 지점의 벽의 정보를 저장했다.
binary[0] : 서쪽 벽이 있는지 없는지 여부, binary[1] : 북쪽, binary[2] : 동쪽, binary[3] : 남쪽 벽이다.
이와 맞춰서 dx, dy 또한 0,1,2,3 인덱스가 서, 북, 동, 남으로 이동하도록 설정했다.
이 문제에서 구할 것은 세가지이다.
1. 전체 방의 개수
2. 최대 방의 크기
3. 벽 하나를 허물어서 얻을 수 있는 최대 방의 크기
1번 2번은 한 번에 구할 수 있다.
일단 전체 방의 개수는 bfs를 호출한 횟수일 것이다. 왜냐하면 bfs는 방문하지 않은 지점에서만 호출되기 때문이다.
(1,1)부터 bfs를 시작해서 방을 이동하면서 visit 배열에 roomNumber를 기록한다. 첫번째 bfs는 1번 방을 모두 방문, 두번째 bfs는 2번 방을 모두 방문 .. 이런식이다.
현재 위치 (x,y)에서 다음 점 (nx,ny)을 방문할 땐 벽이 있으면 안 된다. 현재 지점 (x,y)의 벽 정보를 얻기 위해 bi(x,y)를 호출해서 binary[4] 배열을 최신화하자. binary[i]가 1이면 방문할 수 없으니 continue하고 0이면 방문한다.
그 후 큐에 있는 모든 점을 방문하면서 visit배열에 roomNumber를 기록한다. 또한 tmpRoomSize를 통해 방의 크기를 구한다. 방문하지 않은 같은 방을 방문할 때마다 방의 크기를 1씩 늘린다. 그 후 모든 점을 방문하고 bfs를 끝내기 전에 room[] 배열에 지금 방의 크기를 기록하고, maxRoomSize를 최신화한다. maxRoomSize는 2번 답, 즉 최대 방의 크기를 구하기 위한 변수이다.
bfs를 통해 1번과 2번을 구했다. 1번 2번을 했으면 거의 다 푼거나 마찬가지다.
예시 입력의 visit 배열을 출력한다면
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
이 될 것이다. 이게 우리가 바라던 지도의 모습이다.
3번을 구하려면 어떻게 해야할까.
다른 블로그를 살펴보니 각 지점에서 벽을 하나씩 부수면서 최대 값을 구하고 그러던데, 그럴 필요 없다.
그냥 맞닿은 다른 방의 크기를 합해보면 된다.
이게 무슨 소리냐 하면 예시 visit배열에서 1과 2, 1과 5는 맞닿아 있다. 따라서 둘이 닿는 지점에서 어느 벽을 합하건 방의 크기를 합할 수 있음은 똑같다. 그러나 1번과 3번은 맞닿아있지 않기 때문에 크기를 합할 수 없다.
그러니까 3번을 구하는 방법은 (1,1)부터 모든 지점을 방문하면서 동, 서, 남, 북 중 맞닿은 다음 지점의 방의 번호가 다르면 두 방의 크기를 더해서 최대값과 비교하면 된다는 소리다. 이 크기를 maxSumSize 변수에 저장한다.
bfs2를 통해 모든 지점을 방문하면 1번과 5번의 방의 크기를 합한 16이 답임을 알 수 있다.
벽을 각각 부수고 크기를 구하는 방법은 너무 복잡하고 어려워 보이지만 이 방법은 그냥 더하면 되므로 더 간편하다.
1,2,3번을 모두 구했으니 출력만 하면 된다.
주의해야할 점으로는 각 방의 크기를 저장하는 배열 room의 크기를 2501 이상으로 해줘야 한다는 것이다.
N과 M이 최대 50까지 가능하므로 최대 2500개의 방이 생길 수 있다. 따라서 index상 1을 더해 2501 이상으로 해주자.
글 맨 아래에 백준에서 얻은 테스트 케이스를 올려두었다.
풀면서 참고해보자.
코드 원본 : https://github.com/chosh95/STUDY/blob/master/BaekJoon/2020/%EC%84%B1%EA%B3%BD%20(2234%EB%B2%88).cpp
C++ 코드
#include <iostream>
#include <queue>
using namespace std;
int N, M;
int visit[51][51]; // 방의 번호 부여
int visit2[51][51]; // 방의 연결 여부를 알기 위한 방문 배열
int p[51][51]; // 맨 처음 입력받는 벽의 정보
int dx[4] = { 0,-1,0,1 }; //서, 북, 동, 남
int dy[4] = { -1,0,1,0 };
int binary[4]; // p[i][j]의 벽 정보. 서, 북, 동, 남에 벽이 있으면 1 없으면 0
int roomNumber = 0, maxRoomSize = 0, maxSumSize = 0 ; // 전체 방의 개수, 최대 방의 크기, 최대 합한 방의 크기
int room[2501]; // room[i] : i번째 방의 크기
void bi(int a, int b) {
int cur = p[a][b];
int cnt = 0;
while (cnt<4) {
binary[cnt] = 0;
int rest = cur % 2;
cur /= 2;
if (rest == 1)
binary[cnt] = 1;
cnt++;
}
}
void bfs(int a, int b) {
queue<pair<int, int>> q;
q.push({ a,b });
visit[a][b] = roomNumber;
int tmpRoomSize = 1;
while (!q.empty()) {
int x = q.front().first;
int y = q.front().second;
q.pop();
bi(x, y);
for (int i = 0; i < 4; i++) {
if (binary[i] == 1) continue;
int nx = x + dx[i];
int ny = y + dy[i];
if (nx<1 || ny<1 || nx>N || ny>M) continue;
if (visit[nx][ny] == 0) {
visit[nx][ny] = roomNumber;
q.push({ nx,ny });
tmpRoomSize++;
}
}
}
room[roomNumber] = tmpRoomSize;
maxRoomSize = max(maxRoomSize, tmpRoomSize);
}
void bfs2()
{
visit2[1][1] = 1;
queue<pair<int, int>> q;
q.push({1,1});
while (!q.empty()) {
int x = q.front().first;
int y = q.front().second;
q.pop();
int curRoomNumber = visit[x][y];
for (int i = 0; i < 4; i++) {
int nx = x + dx[i];
int ny = y + dy[i];
if (nx<1 || ny<1 || nx>N || ny>M) continue;
if (visit2[nx][ny] == 0) {
q.push({ nx,ny });
visit2[nx][ny] = 1;
int nextRoomNumber = visit[nx][ny];
if (curRoomNumber != nextRoomNumber) {
maxSumSize = max(maxSumSize, room[curRoomNumber] + room[nextRoomNumber]);
}
}
}
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin >> M >> N;
for (int i = 1; i <= N; i++)
for (int j = 1; j <= M; j++)
cin >> p[i][j];
for (int i = 1; i <= N; i++)
for (int j = 1; j <= M; j++)
if (visit[i][j] == 0) {
roomNumber++;
bfs(i, j);
}
bfs2();
cout << roomNumber << "\n";
cout << maxRoomSize << "\n";
cout << maxSumSize;
}
5 4
11 14 7 11 6
3 14 5 15 5
5 15 5 3 12
9 14 13 13 15
7
6
10
10 5
3 10 10 2 10 10 2 10 10 6
1 6 3 4 3 6 1 6 3 4
1 4 1 4 1 4 1 4 1 4
1 12 9 4 9 12 1 12 9 4
9 10 10 8 10 10 8 10 10 12
2
44
50
10
10
11 10 10 14 7 3 10 2 2 6
3 2 2 6 5 1 2 0 0 4
1 0 0 4 5 1 0 0 0 4
1 0 0 4 13 9 8 8 8 4
1 0 0 4 7 11 10 10 14 13
1 0 0 4 5 7 3 2 2 6
1 0 0 4 5 5 1 0 0 4
1 0 0 4 13 5 1 0 0 4
1 0 0 4 7 5 1 0 0 4
9 8 8 12 13 13 9 8 8 12
9
36
41
15 14
11 14 3 6 3 6 3 6 3 6 3 6 11 2 6
3 10 12 9 12 9 12 9 12 9 12 9 6 1 4
13 7 11 10 10 10 10 10 10 14 11 6 5 1 4
11 4 3 10 10 10 10 10 10 10 6 5 13 1 4
7 13 5 7 11 10 2 10 14 7 5 13 7 9 12
1 14 5 1 10 14 5 11 10 4 9 6 1 10 6
13 7 5 5 3 10 8 10 6 5 3 12 9 10 12
11 4 5 13 5 3 10 6 5 13 5 3 10 10 6
7 13 1 10 4 1 10 4 1 10 4 5 3 10 12
1 14 5 7 5 9 10 12 5 7 5 5 9 10 6
13 7 13 5 9 10 2 10 12 13 13 5 3 10 12
7 5 15 9 10 14 5 11 14 11 14 5 9 10 6
5 13 7 7 11 10 8 10 14 7 3 12 3 10 12
13 15 13 13 11 10 14 11 10 12 9 10 8 10 14
27
55
85
50
50
7 15 7 3 14 11 10 10 14 3 2 2 6 15 7 7 7 7 11 2 6 3 10 2 6 15 3 14 3 10 10 10 6 11 10 2 14 7 7 11 14 3 14 7 7 15 11 14 15 7
1 14 9 0 10 14 15 7 7 13 9 8 8 2 0 12 9 0 2 4 13 1 14 5 9 6 9 14 13 7 15 7 13 3 10 0 2 4 13 15 11 4 15 13 13 11 10 10 6 5
13 15 11 8 14 11 6 5 13 3 6 15 11 12 1 14 15 1 12 9 6 1 6 1 10 4 11 6 3 8 2 4 7 13 3 12 13 13 3 6 15 9 2 6 3 14 7 7 1 12
7 3 14 7 3 14 5 1 2 0 4 15 11 14 13 11 2 0 14 11 12 1 0 8 6 1 2 12 5 15 5 1 8 14 13 11 2 2 4 1 6 11 12 13 1 14 9 12 5 7
9 0 14 1 8 2 8 0 4 1 4 3 2 14 7 7 5 13 11 14 3 12 9 10 4 9 0 14 1 2 0 0 10 6 11 10 4 1 4 9 0 14 15 15 9 10 10 10 0 12
7 9 6 13 3 12 15 9 4 5 13 1 4 15 1 8 4 3 2 2 0 6 7 15 5 15 9 2 12 1 12 5 11 4 7 7 1 8 8 6 5 11 10 6 15 15 11 14 5 7
13 7 5 15 13 7 11 6 5 13 15 13 1 2 12 15 5 9 8 12 5 1 0 2 8 10 10 4 15 5 15 13 11 4 5 1 12 15 3 12 9 2 6 9 14 7 3 6 5 13
11 8 0 6 15 9 2 8 12 11 6 3 12 9 2 2 4 11 6 15 9 8 4 1 14 7 15 5 15 1 6 11 2 0 8 0 14 15 5 15 7 13 5 15 15 9 8 0 12 7
7 7 13 13 3 6 13 11 2 2 12 9 14 11 8 0 4 11 8 14 3 14 1 4 3 12 3 4 3 4 9 10 0 12 7 5 7 11 12 15 1 10 8 10 14 7 11 8 2 4
9 8 2 2 8 8 2 14 9 4 15 7 3 6 11 8 8 6 15 15 5 7 9 4 13 7 5 5 9 0 10 10 8 10 0 8 12 7 11 10 12 15 3 10 2 0 10 6 5 13
15 7 5 13 15 11 12 7 15 9 6 5 9 12 7 7 11 8 6 11 0 0 6 13 11 12 9 12 11 8 10 14 11 10 8 6 3 12 7 11 2 14 5 11 4 13 3 8 12 15
15 5 1 6 3 6 15 5 3 2 0 4 11 14 9 0 14 11 0 6 5 13 5 11 6 11 10 14 11 10 14 15 15 3 6 13 13 11 4 7 1 6 1 2 0 2 12 15 11 14
15 1 12 5 5 13 7 1 0 4 5 5 7 11 6 5 11 10 8 12 5 3 12 7 5 15 15 15 15 11 14 15 15 13 5 7 11 6 5 13 13 1 0 0 8 8 2 2 14 7
11 12 7 1 8 6 1 12 9 4 1 12 5 11 8 4 3 2 10 14 9 0 6 13 5 15 15 15 3 2 6 3 2 2 8 4 7 9 0 6 15 5 1 4 11 6 9 0 2 12
7 11 8 0 10 8 4 7 3 0 4 15 9 10 10 0 0 4 3 10 6 13 13 11 8 10 14 11 12 5 9 4 1 8 6 13 9 6 13 1 2 12 9 12 3 4 3 0 0 6
1 10 14 9 10 6 1 12 9 12 5 15 7 3 10 12 5 13 5 15 5 11 2 14 7 3 10 14 7 5 7 1 12 15 13 3 14 9 10 4 1 14 7 3 12 9 12 1 12 5
5 11 6 11 14 1 4 7 7 15 1 6 5 9 2 14 9 14 9 10 0 2 8 14 9 8 2 14 13 9 4 5 11 2 10 8 6 3 14 9 4 3 12 9 6 3 6 13 15 13
13 15 5 11 2 12 1 12 5 15 9 8 8 10 8 14 11 14 7 11 0 12 11 10 6 11 12 7 7 7 13 9 10 4 15 7 5 13 3 14 13 1 14 11 8 0 8 6 15 7
3 2 8 14 5 3 0 6 13 15 11 2 2 6 7 3 14 7 13 3 4 11 14 11 0 10 6 13 1 4 7 15 11 4 11 8 8 6 1 6 15 9 10 6 3 12 15 1 6 5
1 8 10 14 9 4 1 4 3 2 6 1 8 8 4 5 15 5 15 9 0 2 6 11 12 3 4 7 1 4 9 10 2 0 6 11 14 1 12 9 6 3 2 8 8 2 2 0 4 5
9 6 7 3 6 1 8 8 12 9 8 4 3 10 8 0 14 13 3 2 12 5 9 6 15 5 9 0 0 0 10 2 12 5 9 6 3 0 6 3 8 8 0 6 15 5 13 1 4 13
7 9 8 4 13 9 2 2 14 3 6 1 8 2 14 13 15 15 1 8 10 0 10 12 3 12 3 0 0 12 15 9 6 1 10 0 12 13 1 4 3 2 8 0 10 0 10 0 8 14
13 11 10 4 11 6 13 1 6 5 5 1 6 1 6 7 11 14 5 15 7 5 7 11 0 14 9 4 13 11 2 14 9 12 3 0 14 3 4 9 4 1 2 4 11 8 14 5 15 15
11 2 6 1 2 12 3 8 4 5 1 0 8 4 13 1 2 2 0 6 1 8 12 3 4 11 6 9 6 3 8 10 2 14 1 4 15 9 4 3 4 5 5 1 10 6 7 13 15 15
3 12 9 4 9 2 4 7 5 5 13 5 3 4 11 8 8 8 12 1 4 11 10 0 4 3 8 2 8 12 7 11 0 10 8 4 11 10 8 12 13 13 1 12 15 1 4 11 2 14
5 3 2 4 15 5 13 13 1 8 6 13 1 0 2 14 3 2 14 5 9 6 7 5 5 5 11 0 6 7 13 3 12 11 10 4 7 11 6 11 10 10 4 15 11 0 4 15 1 14
1 4 9 12 3 4 7 3 0 10 8 10 12 1 0 6 13 5 15 9 6 13 9 12 1 0 10 4 9 0 14 13 7 15 11 12 1 14 1 6 3 6 9 14 11 4 13 7 13 7
13 5 15 11 0 8 12 1 0 2 2 6 11 4 9 0 6 9 10 14 13 3 6 7 5 1 6 5 11 4 11 2 8 14 3 6 13 15 1 12 1 4 11 14 7 13 7 9 10 4
11 12 7 11 12 15 3 12 5 13 1 12 7 9 14 1 0 10 10 2 2 0 8 8 12 5 5 13 7 5 15 9 6 11 4 1 14 3 4 3 8 8 6 7 1 14 13 11 2 12
3 10 12 3 2 2 0 10 0 2 12 3 0 10 6 9 8 10 10 0 8 12 7 11 14 1 12 3 12 5 3 2 8 14 1 8 2 8 12 1 14 11 8 12 9 6 15 11 8 6
9 14 15 13 5 13 13 15 5 13 3 4 5 15 5 11 10 14 7 1 6 15 9 2 2 8 6 13 11 4 13 9 10 14 9 6 9 10 10 4 3 10 10 10 10 8 2 14 3 12
15 3 14 11 0 6 15 15 13 15 9 8 0 10 4 7 11 2 8 4 13 3 10 0 12 11 0 10 2 0 2 6 3 14 11 4 3 2 14 13 13 11 14 3 6 3 8 10 4 7
7 9 6 11 12 13 3 2 10 6 15 7 13 11 8 4 7 13 3 4 15 5 15 5 7 3 8 6 1 4 5 9 0 10 10 4 9 8 10 14 3 6 7 13 1 8 10 6 1 4
9 14 13 3 6 7 1 4 11 8 14 1 6 11 6 9 4 3 4 5 15 9 14 1 8 4 15 9 0 0 12 7 13 7 3 12 7 15 3 6 5 13 9 14 13 11 14 9 4 5
15 15 15 13 13 9 4 13 15 11 14 9 0 14 9 6 5 5 9 12 11 2 6 9 6 5 15 11 0 8 2 4 11 12 1 10 12 15 13 1 8 6 3 2 2 2 10 10 12 5
3 6 15 3 10 10 12 7 3 10 2 6 1 14 15 13 5 13 15 11 2 8 8 6 13 5 15 3 8 6 13 13 11 14 9 14 7 15 11 4 7 9 4 13 9 12 3 14 15 5
5 9 6 9 14 3 14 1 0 6 9 4 9 6 15 15 13 7 15 11 12 11 14 5 3 12 3 8 2 8 10 10 10 10 14 3 8 6 15 9 0 10 12 11 6 7 9 2 10 4
9 2 12 15 11 8 14 1 0 4 7 13 3 0 6 11 6 9 2 10 14 15 11 4 9 2 8 14 9 6 11 6 11 2 2 0 6 13 15 15 1 2 6 3 4 9 14 13 11 4
3 4 11 14 3 10 2 4 9 4 5 15 9 12 1 6 13 7 9 2 14 7 15 9 10 12 11 14 15 9 14 9 14 9 12 1 4 15 3 10 4 5 5 1 4 3 2 10 14 5
9 4 11 10 4 11 12 13 15 5 1 2 10 2 12 1 10 4 11 4 15 13 11 2 10 10 2 6 7 3 14 11 2 2 6 13 5 11 12 7 9 12 9 12 13 13 9 10 10 12
15 9 14 15 9 2 6 7 15 13 5 9 14 13 3 12 7 13 3 4 15 7 3 12 11 6 9 4 13 1 10 14 5 1 12 3 0 14 15 9 10 6 11 2 6 15 15 7 11 6
7 7 7 15 3 0 8 4 3 14 9 2 10 14 1 14 9 2 8 0 6 5 1 2 6 9 10 4 3 8 2 2 4 13 11 0 4 11 6 15 3 0 2 4 9 6 11 8 2 4
13 1 0 6 5 13 11 8 4 3 10 4 7 15 1 14 3 8 6 9 0 8 8 12 1 6 15 9 0 10 0 0 0 14 11 12 5 15 9 2 12 9 8 4 11 12 15 7 5 13
7 1 4 1 12 11 10 14 9 12 3 8 12 11 4 15 1 14 5 7 9 6 15 15 9 8 14 3 0 10 4 5 1 6 15 15 13 11 2 4 7 7 15 13 15 15 3 0 4 15
1 4 1 4 15 7 3 14 7 7 9 6 15 11 8 2 8 2 4 9 2 8 6 15 15 7 15 13 5 3 12 13 1 4 3 6 7 11 12 5 13 5 11 2 6 15 1 0 8 14
13 9 8 12 7 1 0 14 13 9 14 1 10 2 6 1 14 13 1 6 1 2 8 10 6 1 10 10 0 12 11 14 1 0 12 1 12 11 2 12 15 1 10 4 1 10 12 5 15 15
3 2 6 7 13 5 13 11 6 11 14 9 6 1 8 0 6 11 12 1 4 5 11 14 9 8 10 14 13 3 14 7 13 5 3 4 7 3 12 15 7 9 2 0 12 7 7 13 11 6
5 9 12 1 6 1 6 3 12 15 11 10 0 12 7 13 13 3 2 8 12 5 3 14 15 7 3 14 7 13 11 4 7 5 5 13 9 4 11 6 5 3 12 1 2 0 12 7 15 13
1 14 15 13 5 13 1 12 3 10 14 11 8 2 8 2 6 1 12 11 6 5 9 2 10 4 5 7 9 14 3 0 0 8 12 7 7 13 15 13 5 9 10 4 9 0 10 8 6 15
13 11 14 15 9 10 8 14 13 15 11 10 14 9 14 9 8 12 15 11 8 8 10 12 15 13 13 13 15 11 12 9 12 11 14 13 9 14 11 10 8 14 15 9 10 12 15 15 9 14
306
905
1233
'알고리즘 > 백준' 카테고리의 다른 글
| [백준] 중량제한 (1939번) (0) | 2020.06.16 |
|---|---|
| [백준] 양 (3184번) (0) | 2020.06.16 |
| [백준] 절댓값 힙(11286번) (0) | 2020.06.11 |
| [백준] 신나는 함수 실행(9184번) (0) | 2020.06.07 |
| [백준] 가로수 (2485번) (0) | 2020.06.06 |