백준 2234 성곽 풀이(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의 답을 출력한다.

 

#include <iostream>
#include <vector>
#include <climits>
#include <string>
#include <algorithm>

using namespace std; 

int N, M, iRoomCount, iRoomExtent = 1, iMaxExtent = 0;
int castle[51][51];
int roomNum[51][51];
int visited[51][51];

const int dy[] = { 0, -1, 0, 1 };
const int dx[] = { -1, 0, 1, 0 };

vector<int> vRoomSize;

int Dfs(int y, int x, int depth)
{
	visited[y][x] = 1;
	roomNum[y][x] = iRoomCount;
	int dir = 0;
	for (int i = 1; i < 16; i *= 2, ++dir)
	{
		if (!(castle[y][x] & i))
		{
			int ny = y + dy[dir];
			int nx = x + dx[dir];
			if (ny<0 || nx <0 || ny >= M || nx >= N ||visited[ny][nx])
				continue;
			depth = Dfs(ny, nx, depth+1);
		}
	}

	return depth;
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	cin >> N >> M;

	for (int i = 0; i < M; ++i)
	{
		for (int j = 0; j < N; ++j)
		{
			cin >> castle[i][j];
		}
	}

	for (int i = 0; i < M; ++i)
	{
		for (int j = 0; j < N; ++j)
		{
			if (visited[i][j])
				continue;
			vRoomSize.push_back((Dfs(i, j, 1)));
			iRoomCount++;
		}
	}
	

	//fill(&visited[0][0], &visited[0][0] + 51 * 51, 0);

	for (int i = 0; i < M; ++i)
	{
		for (int j = 0; j < N; ++j)
		{
			int dir = 0;
			for (int k = 1; k < 16; k *= 2, ++dir)
			{
				if ((castle[i][j] & k))
				{
					int ny = i + dy[dir];
					int nx = j + dx[dir];
					if (ny < 0 || nx < 0 || ny >= M || nx >= N)
						continue;
					if (roomNum[i][j] == roomNum[ny][nx])
						continue;

					iRoomExtent = max(iRoomExtent, vRoomSize[roomNum[i][j]] + vRoomSize[roomNum[ny][nx]]);
				}
			}
		}
	}

	sort(vRoomSize.begin(), vRoomSize.end(), greater<>());
	iMaxExtent = vRoomSize.front();

	cout << iRoomCount <<" " << iMaxExtent<< " "<< iRoomExtent;

	return 0;
}

 

DFS 를 이용해 각 방의 크기와 최대 크기를 구하였고

방들을 구할때마다방들 좌표에 방 번호를 부여 하였다. 그리고 각 방을 돌면서 벽이있을경우 허물어 보고 양 벽에 넘버링 된 값으로 방크기를 가져와 더하면서 허물었을때의 방 최고 크기를 구하였다.