[C++] 백준(BOJ) -2234 : 성곽

01 Dec 2023 in Develop on C++, Algorithm Last modified at: 2024-05-20

인프런에 있는 큰돌님의 강의 10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트를 듣고 정리한 필기입니다.

• 문제
• 입력
• 출력
• 알고리즘
• 풀이
• 코드
• 평가

문제

BOJ - 2234 : 성곽(링크)

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

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. DFS
2. Connected Component
3. 비트마스킹
4. 완전탐색

풀이

1. 구해야 하는 3가지 변수
   • 이 성에 있는 방의 개수 : cnt
   • 가장 넓은 방의 넓이 : mx
   • 하나의 벽을 제거하여 얻을 수 있는 가장 넓은 방의 크기 : big
2. Connected Component를 이용해 각 Component에 ID(cnt)를 부여한다
3. DFS를 통해 뚫려 있으면 탐색 하게 코드 구현
4. compSize[cnt] 를 이용하여 big 값을 완전 탐색을 통해 구현

코드

// BOJ - 2234 : 성곽
#include<bits/stdc++.h>
using namespace std;

// 서쪽을 1, 남쪽을 8로 문제에서 설정
const int dy[] = { 0, -1, 0, 1 };
const int dx[] = { -1, 0 ,1 ,0 };

int n, m, a[54][54], visited[54][54], cnt, res, compSize[2504], big, mx;

int dfs(int y, int x, int cnt)
{
	if(visited[y][x]) return 0;
	visited[y][x] = cnt;
	int res = 1;

	for (int i = 0; i < 4; i++)
	{
		if (!(a[y][x] & (1 << i))) // 뚫려있으면 탐색한다
		{
			int ny = y + dy[i];
			int nx = x + dx[i];
			res += dfs(ny, nx, cnt);
		}
	}
	return res;
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	
	cin >> m >> n;

	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
		{
			cin >> a[i][j];
		}
	}

	// 구역 설정 DFS, Connected Component
	// cnt, mx 값 구하기
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
		{
			if (!visited[i][j])
			{
				cnt++;
				compSize[cnt] = dfs(i, j, cnt);
				mx = max(mx, compSize[cnt]);
			}
		}
	}

	// 완전탐색으로 big 값 구하기
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
		{
			// y축 오버플로우 체크
			if (i + 1 < n)
			{
				int a = visited[i + 1][j];
				int b = visited[i][j];
				if (a != b) big = max(big, compSize[a] + compSize[b]); // 다른 영역 일 때 벽 부수기고 big 값 비교 후 갱신
			}
			if (j + 1 < m)
			{
				int a = visited[i][j + 1];
				int b = visited[i][j];
				if (a != b) big = max(big, compSize[a] + compSize[b]);
			}
		}
	}

	cout << cnt << '\n' << mx << '\n' << big << '\n';

	return 0;
}

평가

• DFS, Connected Component, 비트마스킹, 완전 탐색 모든 내용이 총 집합된 바이블 같은 문제이다 반복 숙달하여 완전하게 나의 코드로 만들 수 있도록 연습이 필요