이번에는 백준 2234번 성곽 문제를 풀어보았습니다.
문제를 처음 봤을 때 방의 개수와 가장 큰 방의 크기를 구하는 부분은 연결된 컴포넌트를 찾는 문제라고 생각했습니다.
또한 벽 하나를 제거했을 때 가장 큰 방을 구해야 했기 때문에, 먼저 모든 방을 번호로 구분한 뒤 인접한 서로 다른 방을 합치는 방식으로 구현하였습니다.
문제 설명
각 칸에는 벽의 정보가 비트 형태로 저장되어 있습니다.
- 서쪽 : 1
- 북쪽 : 2
- 동쪽 : 4
- 남쪽 : 8
이를 이용하여
- 방의 개수
- 가장 넓은 방의 크기
- 벽 하나를 제거했을 때 가장 넓은 방의 크기
를 구하는 문제입니다.
풀이 아이디어
먼저 DFS를 이용하여 연결된 방을 모두 찾았습니다.
각 연결된 컴포넌트마다 번호를 부여하고, 방의 크기를 저장하였습니다.
이후 다시 전체 지도를 순회하면서 벽이 존재하는 방향을 확인하였습니다.
벽 너머가 다른 방이라면 두 방을 합칠 수 있으므로 두 방의 크기를 더하여 최댓값을 갱신하였습니다.
코드
#include <bits/stdc++.h>
using namespace std;
int inp[50][50];
int room_num[50][50];
int N,M;
bool visited[50][50];
int dy[4] = {0,-1,0,1};
int dx[4] = {-1,0,1,0};
int ret[3];
vector<int> room_size;
int dfs(int y, int x, int rn) {
int ret_val = 1;
for (int i=0; i<4; i++) {
int ny = dy[i] + y;
int nx = dx[i] + x;
if (ny < 0 || nx < 0 || ny >= N || nx >= M || visited[ny][nx]) continue;
if (inp[y][x] & (1 << i)) continue;
visited[ny][nx] = true;
room_num[ny][nx] = rn;
ret_val += dfs(ny, nx, rn);
}
return ret_val;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
cin >> M >> N;
for (int i=0; i<N; i++) {
for (int j=0; j<M; j++) {
cin >> inp[i][j];
}
}
for (int i=0; i<N; i++) {
for (int j=0; j<M; j++) {
if (!visited[i][j]) {
visited[i][j] = true;
room_num[i][j] = ret[0];
int room = dfs(i, j, ret[0]);
ret[0]++;
room_size.push_back(room);
ret[1] = max(ret[1], room);
}
}
}
for (int i=0; i<N; i++) {
for (int j=0; j<M; j++) {
for (int k=0; k<4; k++) {
int ny = i + dy[k];
int nx = j + dx[k];
if (ny < 0 || nx < 0 || ny >= N || nx >= M) continue;
if (!(inp[i][j] & (1 << k))) continue;
int room_a = room_num[ny][nx];
int room_b = room_num[i][j];
if (room_a == room_b) continue;
ret[2] = max(ret[2], room_size[room_a] + room_size[room_b]);
}
}
}
for (int i=0; i<3; i++) {
cout << ret[i] << '\n';
}
return 0;
}풀이 흐름
- 지도를 입력받습니다.
- DFS를 이용하여 연결된 방을 찾습니다.
- 각 방마다 번호를 부여하고 방의 크기를 저장합니다.
- 가장 큰 방의 크기를 갱신합니다.
- 다시 전체 지도를 순회합니다.
- 벽이 있는 방향을 확인합니다.
- 벽 너머가 다른 방이라면 두 방의 크기를 더하여 최댓값을 갱신합니다.
- 결과를 출력합니다.
구현 포인트
1. 연결된 방 찾기
DFS를 이용하여 연결된 방을 찾았습니다.
if (inp[y][x] & (1 << i)) continue;현재 방향에 벽이 존재한다면 이동하지 않았습니다.
벽이 없는 경우에만 DFS를 계속 수행하였습니다.
2. 비트를 이용한 벽 확인
입력값은 벽의 정보를 비트로 저장하고 있습니다.
- 서쪽 : 첫 번째 비트
- 북쪽 : 두 번째 비트
- 동쪽 : 세 번째 비트
- 남쪽 : 네 번째 비트
이를 그대로 사용하기 위해 이동 방향 역시 같은 순서로 선언하였습니다.
int dy[4] = {0,-1,0,1};
int dx[4] = {-1,0,1,0};따라서
inp[y][x] & (1 << i)만으로 해당 방향에 벽이 존재하는지 바로 확인할 수 있었습니다.
3. 방 번호 저장
연결된 컴포넌트마다 번호를 부여하였습니다.
room_num[ny][nx] = rn;또한 각 방의 크기는 따로 저장하였습니다.
room_size.push_back(room);이후 벽을 제거하는 과정에서 사용하였습니다.
4. 벽 하나 제거했을 때의 최대 크기 계산
전체 지도를 다시 순회하면서 벽이 존재하는 방향만 확인하였습니다.
if (!(inp[i][j] & (1 << k))) continue;벽 너머가 다른 방이라면
room_size[room_a] + room_size[room_b]를 계산하여 최댓값을 갱신하였습니다.
ret[2] = max(ret[2], room_size[room_a] + room_size[room_b]);5. 세 가지 정답 관리
ret 배열을 이용하여 문제에서 요구하는 세 가지 값을 관리하였습니다.
ret[0]: 방의 개수ret[1]: 가장 넓은 방의 크기ret[2]: 벽 하나를 제거했을 때 가장 넓은 방의 크기
각 값을 계산하면서 순차적으로 갱신하도록 구현하였습니다.
