성곽
문제 해석
MxN크기의 성곽이 있을 때 다음 정보를 계산하는 문제입니다.
- 이 성에 있는 방의 개수
- 가장 넓은 방의 넓이
- 하나의 벽을 제거하여 얻을 수 있는 가장 넓은 방의 크기
각 칸의 4방향에 벽이 있는지 여부에 대한 정보가 이진수의 비트 형태로 주어집니다.
각 서,북,동,남쪽의 벽이 있는지 여부는 1,2,4,8로 대체됩니다.
설계(20)
아주 재미있는 BFS알고리즘 문제입니다.
먼저 조건 1,2와 3을 나누어서 생각해야합니다.
1,2의 경우 모든 칸을 탐색하면서 벽을 뚫지 않고 이동가능한 모든곳을 bfs알고리즘으로 탐색합니다. 이와 동시에 각 구역을 인덱스화해줍니다.
벽의 상태가 비트형태로 되어있기 때문에 비트연산으로 이동가능한 곳을 탐색하면 됩니다.
각 구역의 넓이를 배열에 따로 저장해놓습니다.
위와 같이 구현할 경우 원하는 출력 1,2를 얻을 수 있습니다.
3번째 출력의 경우 나눠져 있는 구역들의 4방향 중, 다른 구역인 곳이 있는 부분을 찾아야 합니다.
위 조건을 만족하는 좌표를 찾는 이유는 서로 다른 구역이지만 벽을 한번 뚫는 경우를 생각해야하기 때문입니다.
만약 조건에 맞는 좌표를 찾으면 현재 구역+인접한 구역의 넓이를 더한 값으로 최댓값을 갱신해주면 출력 3을 얻을 수 있습니다.
구현(40)
코드
#include <iostream>
#include <queue>
#include <algorithm>
#include <cstring>
using namespace std;
#define MAXN 51
int N, M;
int arr[MAXN][MAXN];
int dist[MAXN][MAXN];
int cost[MAXN * MAXN];
int dx[] = { 0,-1,0,1 };
int dy[] = { -1,0,1,0 };
queue<pair<int,int> > q;
int cnt,max_v,total_max_v;
int bfs(int x, int y) {
int sum = 1;
q.push({ x,y});
dist[x][y] = cnt;
while (!q.empty()) {
int x = q.front().first;
int y = q.front().second;
q.pop();
for (int k = 0; k < 4; k++) {
int nx = x + dx[k];
int ny = y + dy[k];
if (nx < 0 || ny < 0 || nx >= N || ny >= M) continue;
if (arr[x][y] & (1 << k)) continue;
if (dist[nx][ny] == -1) {
sum++;
dist[nx][ny] = cnt;
q.push({ nx,ny });
}
}
}
return sum;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
memset(dist, -1, sizeof(dist));
cin >> M >> N;
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
cin >> arr[i][j];
}
}
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
if (dist[i][j] == -1) {
cnt++;
cost[cnt] = bfs(i, j);
max_v = max(max_v,cost[cnt]);
}
}
}
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
for (int k = 0; k < 4; k++) {
int nx = i + dx[k];
int ny = j + dy[k];
if (nx < 0 || ny < 0 || nx >= N || ny >= M) continue;
if (dist[i][j] != dist[nx][ny]) {
total_max_v = max(total_max_v, cost[dist[i][j]] + cost[dist[nx][ny]]);
}
}
}
}
cout << cnt << "\n";
cout << max_v << "\n";
cout << total_max_v << "\n";
return 0;
}
디버깅
구현을 하는 도중 아주 많은 실수를 하였습니다.
-
BFS알고리즘으로 탐색하면서 dist배열에 거리를 갱신하는 실수를 하였습니다. 이럴경우 최단거리를 찾는 것이지 해당 구역의 넓이를 구하는 것이 아니게 됩니다.
-
출력 1,2,3을 한번에 구하려고 dist 3차원 배열을 이용하는 논리적 오류를 범했습니다. 벽이 뚫린 경우와 안뚫린 경우의 dist를 구하는 방법을 이용하였지만, 이럴 경우 각 구역의 경계가 모호해져서 원하는 값을 구할 수 없습니다.
-
출력 3을 따로 구현하기 위해서 주먹구구식으로 인덱스 i->j로 갈수 있는지 여부를 체크한 후 cost 2차원배열에 cost[i][j]를 갱신하는 방법을 이용하였습니다.
그러나 위 3번 방법은 각 구역의 인덱스가 50까지만 나온다고 착각했기 때문에 구현한 방법입니다. 최악의 경우 인덱스는 50*50이 나오기 때문에 O((NxM)^3)이라는 어마어마한 시간복잡도로 무조건 시간초과가 날 것입니다.
이를 설계 파트에서 언급한 방법으로 변경하여 O(NxM)으로 시간안에 구현이 가능했습니다.
제출결과
0 ms
마무리
비트연산을 이용하는 bfs알고리즘 문제였습니다.
벽을 한개 뚫었을 때 얻을 수 있는 최대 넓이를 구하는 부분을 생각하는데 오래걸린 문제입니다.