[PS] 백준 2234번 성곽(C/C++)

문제

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

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의 답을 출력한다.

풀이

입력 처리:

1. 주어진 2차원 배열의 방 구조와 크기(N, M)를 입력 받음
2. 각 배열 칸에 벽의 위치를 비트 마스크로 표현할 수 있음.

깊이 우선 탐색 (DFS)으로 방 탐색:

1. 배열을 탐색하면서 아직 방문하지 않은 칸을 발견하면, DFS를 사용하여 해당 방의 크기를 계산
2. DFS는 현재 위치에서 상하좌우로 이동하며 연결된 칸을 탐색합니다. 벽이 있는 방향으로는 이동하지 않음
3. 방문한 칸은 visited 배열에 기록하고, 각 방의 크기를 compSize 배열에 저장

방의 개수와 최대 방 크기 계산:

1. DFS를 통해 탐색된 방의 개수를 세고(room_cnt), 이 중 가장 큰 방의 크기를 찾음(max_area).

인접한 방 합치기:

1. 결국 인접한 두 방을 합쳤을 때 가장 큰 면적을 구하면 됨
2. 탐색이 완료된 후, 배열을 다시 탐색하면서 인접한 칸이 서로 다른 방에 속해 있는 경우, 두 방을 합쳤을 때의 크기를 계산
3. 합쳤을 때의 최대 크기를 max_area_last에 저장

결과 출력:

1. 최종적으로 방의 개수, 가장 큰 방의 크기, 그리고 두 방을 합쳤을 때의 최대 크기를 출력

---

C/C++ 코드

#include <iostream>
using namespace std;
int N, M;
int a[51][51];
int visited[51][51];
int room_cnt = 0;
int max_area = 0;
int max_area_last = 0;
int offset_x[4] = { -1,1,0,0 };
int offset_y[4] = { 0,0,1,-1 };
int masks[4] = {1,4,8,2};
int compSize[2501];
int dfs(int x, int y, int cnt) {
	if (visited[y][x]) return 0;
	visited[y][x] = cnt;
	int ret = 1;
	for (int i = 0; i < 4; ++i) {
		int nx = x+offset_x[i];
		int ny = y+offset_y[i];
		if (nx<0 || nx>N - 1 || ny < 0 || ny >M - 1) continue;
		if (visited[ny][nx]) continue;
		if (a[y][x] & masks[i]) continue;
		ret+=dfs(nx, ny,cnt);
	}
	return ret;
}
int main() {
	cin >> N >> M;
	for (int i = 0; i < M; ++i) {
		for (int j = 0; j < N; ++j) {
			cin >> a[i][j];
		}
	}

	for (int i = 0; i < M; ++i) {
		for (int j = 0; j < N; ++j) {
			if (visited[i][j]) continue;
			room_cnt += 1;
			compSize[room_cnt] = dfs(j,i, room_cnt);
			max_area = max(max_area, compSize[room_cnt]);
		}
	}
	for (int i = 0; i < M; ++i) {
		for (int j = 0; j < N; ++j) {
			if (i + 1 < M) {
				int a = visited[i + 1][j];
				int b = visited[i][j];
				if (a != b) {
					max_area_last = max(max_area_last, compSize[a] + compSize[b]);
				}
			}
			if (j + 1 < N) {
				int a = visited[i][j + 1];
				int b = visited[i][j];
				if (a != b) {
					max_area_last = max(max_area_last, compSize[a] + compSize[b]);
				}
			}


		}
	}
	cout << room_cnt << "\n";
	cout << max_area<< "\n";
	cout << max_area_last << "\n";
	return 0;
}