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

 

우선 추가로 해줄 것은 없고 BFS에 담을 다음 위치는 각 방향에 대한 값을 빼서 0보다 작은 경우 즉 못빼는 경우에 이동 가능.

이동하면서 그루핑하는 작업 해주고 , 하나 부순후에 최대 개수는 다시 맵 전체 탐색하면서 자신과 다른 그룹이 인접해 있을 때 그 합을 기준으로 결정.

 

#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
#include<string.h>
using namespace std;

int num[2501];
int arr[50][50];
int group[50][50];
bool visit[50][50];
int dir[4] = { 8,4,2,1 };
// 0 남, 1 동 , 2 북 , 3 서
int N, M;

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

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

	int grp = 0;
	int maxa = 0;
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < M; j++)
		{
			if (!visit[i][j])
			{
				grp++;
				visit[i][j] = true;
				group[i][j] = grp;
				queue<pair<int, int> > que;
				que.push({ i,j });

				int count = 1;

				while (!que.empty())
				{
					int y = que.front().first;
					int x = que.front().second;
					int temp = arr[que.front().first][que.front().second];
					que.pop();

					for (int k = 0; k < 4; k++)
					{
						if (temp - dir[k] < 0)
						{
							int newy = y + dy[k];
							int newx = x + dx[k];
							if (newy >= 0 && newy < N && newx >= 0 && newx < M)
							{
								if (!visit[newy][newx])
								{
									count++;
									visit[newy][newx] = true;
									group[newy][newx] = grp;
									que.push({ newy,newx });
								}
							}
						}
						else
						{
							temp -= dir[k];
						}
					}
				}
				num[grp] = count;
				if (count > maxa)
				{
					maxa = count;
				}
			}
		}
	}

	int gmaxa = 0;
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < M; j++)
		{
			for (int k = 0; k < 4; k++)
			{
				int newy = i + dy[k];
				int newx = j + dx[k];
				if (newy >= 0 && newy < N && newx >= 0 && newx < M)
				{
					if (group[newy][newx] != group[i][j])
					{
						if (gmaxa < num[group[newy][newx]] + num[group[i][j]])
						{
							gmaxa = num[group[newy][newx]] + num[group[i][j]];
						}
					}
				}
			}
		}
	}

	cout << grp << endl;
	cout << maxa << endl;
	cout << gmaxa << endl;
}