[BOJ/백준 2234/C++] 성곽

https://www.acmicpc.net/problem/2234

2234번: 성곽

 

[문제 요약]

- 위의 그림과 같이 성곽이 있다. 굵은 선은 벽을 의미하고, 점선은 지나갈 수 있다. 다음 3가지 값을 구하시오

• 이 성의 있는 방의 개수
• 가장 넓은 방의 넓이
• 하나의 벽을 제거하여 얻을 수 있는 가장 넓은 방의 크기

 

[문제 조건]

- 첫째 줄에 두 정수 N, M이 주어진다. (1 ≤ M, N ≤ 50)

- 벽에 대한 정보는 한 정수로 주어지는데, 서쪽에 벽이 있을 때는 1을, 북쪽에 벽이 있을 때는 2를, 동쪽에 벽이 있을 때는 4를, 남쪽에 벽이 있을 때는 8을 더한 값이 주어진다. (이진법)

- 따라서 이 값은 0부터 15까지의 범위 안에 있다.

- 시간 제한 : 2초 

- 메모리 제한 : 128MB

 

[문제 풀이]

이번 문제의 핵심은 3번째 답을 구하는 것이다.

 

1,2번 답은 기존에 해왔던 탐색 알고리즘을 이용하여 쉽게 구할 수 있다. 까다로운 점이라면 동서남북 4방향으로 모두 갈 수 있는 것이 아니라 배열에 벽에 대한 정보가 주어지고 서쪽이 1, 북쪽이 2, 동쪽이 4, 남쪽이 8이라는 값을 가지고 더해진 상태로 주어진다. 예를들어 값이 10이면 이진법으로 나타냈을때 1010(2)이 되니까 이 칸에는 북쪽과 남쪽에 벽이 있다는 뜻이다. 

 

이처럼 값을 잘 분해하여 벽에 대한 정보를 알아내고 DFS나 BFS를 이용하여 탐색을 하고 한 번의 탐색이 끝났을때 방의 넓이를 비교하여 최대값을 갱신해주고, 총 몇번 탐색이 진행되었는지 횟수를 세어주면 방의 개수가 나온다.

 

void dfs(int x, int y)
{
	cnt++;
	vector<int> direct;
	int tmp = mp[y][x];
	int multiple = 1;
	for (int i = 0; i < 4; i++)
	{
		if ((tmp & 1) == 0) direct.push_back(multiple);

		tmp = tmp >> 1;
		multiple *= 2;
	}

	for (int i = 0; i < direct.size(); i++)
	{
		int nx = x + dx[direct[i]];
		int ny = y + dy[direct[i]];

		if (nx < 0 || ny < 0 || nx >= M || ny >= N) continue;
		if (ck[ny][nx] != 0) continue;

		ck[ny][nx] = area_num;
		dfs(nx, ny);
	}
}
/////////////////////////////////////////////
/////////////////////////////////////////////
for (int i = 0; i < N; i++)
{
    for (int j = 0; j < M; j++)
    {
        if (!ck[i][j])
        {
            cnt = 0;
            ck[i][j] = area_num;
            dfs(j, i);
            max_area_cnt++;
            area_num++;
            max_area_size = max(max_area_size, cnt);
        }
    }
}

 

벽에 대한 정보를 추출할때 비트연산을 이용하여 1,2,4,8 중 벽이 없는 방향에 대한 정보를 찾아 direct배열에 추가하여 dfs를 진행하였다.

 

 

1,2번은 금방 해결했지만 문제는 3번 정답이였다.

 

필자는 처음에 모든 벽을 하나씩 허물고 DFS나 BFS를 이용하여 답이 나올 것 같았는데 왠지 모든 벽에 대해서 하면 시간초과가 날 것 같아서 시도해보지는 못했다.

 

그래서 다른 방법을 이용하였는데 위에서 1,2번 정답을 구할때 각 방에 대해 영역에 번호를 메길 수 있고 이 영역에 대한 넓이를 구할 수 있다. 그래서 각 영역별로 서로 인접한 영역 번호를 갖고 있고, 인접한 두 영역의 넓이를 더했을 때 나오는 최대값이 3번에 대한 정답이 된다고 생각하였다.

 

간단히 쉽게 그림으로 설명하자면

문제에서 주어진 성곽을 DFS를 한번 돌때마다 같은 숫자들로 채워지게 된다.(색으로 구분)

이때 오른쪽 배열은 왼쪽배열을 차례대로 확인하면서 인접한 상하좌우 영역의 번호들을 모두 o로 변경해준다. 예로들어 3행 4열의 값을 기준으로하면 인접한 1,2,3번 영역 ( 오른쪽배열의 area_list[5][1], area_list[5][2], area_list[5][3] 을 o로 체크해준다.)

 

여기서 오른쪽 배열을 이용하여 인접한 두 영역의 넓이의 합의 최대를 계속 갱신하면 마지막에 3번에 대한 정답이 나오게 된다.

 

[소스 코드]

#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <cmath>
#include <deque>
#include <list>
#include <math.h>
#include <map>
#include <queue>
#include <stack>

using namespace std;

int N, M, cnt;
int area_num = 1;
int max_area_size = 0;
int max_area_cnt = 0;
//1 = 서 , 2 = 북 , 4 = 동 , 8 = 남
int dx[9] = { 0,-1,0,0,1,0,0,0,0 };
int dy[9] = { 0,0,-1,0,0,0,0,0,1 };
int dx2[4] = { 0, 1, 0 , -1 };
int dy2[4] = { -1,0,1,0 };
vector<vector<int>> mp;
vector<vector<int>> ck;
vector<vector<int>> area_list;
vector<int> area_area;

void dfs(int x, int y)
{
	cnt++;
	vector<int> direct;
	int tmp = mp[y][x];
	int multiple = 1;
	for (int i = 0; i < 4; i++)
	{
		if ((tmp & 1) == 0) direct.push_back(multiple);

		tmp = tmp >> 1;
		multiple *= 2;
	}

	for (int i = 0; i < direct.size(); i++)
	{
		int nx = x + dx[direct[i]];
		int ny = y + dy[direct[i]];

		if (nx < 0 || ny < 0 || nx >= M || ny >= N) continue;
		if (ck[ny][nx] != 0) continue;

		ck[ny][nx] = area_num;
		dfs(nx, ny);
	}
}

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

	cin >> M >> N;
	mp.resize(N);
	for (int i = 0; i < N; i++) mp[i].resize(M);
	ck.resize(N);
	for (int i = 0; i < N; i++) ck[i].resize(M);

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

	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < M; j++)
		{
			if (!ck[i][j])
			{
				cnt = 0;
				ck[i][j] = area_num;
				dfs(j, i);
				max_area_cnt++;
				area_num++;
				max_area_size = max(max_area_size, cnt);
				area_area.push_back(cnt);
			}
		}
	}

	int area_cnt = area_area.size();
	area_list.resize(area_cnt);
	for (int i = 0; i < area_cnt; i++) area_list[i].resize(area_cnt);

	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < M; j++)
		{
			for (int k = 0; k < 4; k++)
			{
				int nx = j + dx[k];
				int ny = i + dy[k];

				if (nx < 0 || ny < 0 || nx >= M || ny >= N) continue;

				area_list[ck[i][j] - 1][ck[ny][nx] - 1] = 1;
				area_list[ck[ny][nx] - 1][ck[i][j] - 1] = 1;
			}
		}
	}
	int break_max_area = 0;
	for (int i = 0; i < area_cnt; i++)
	{
		for (int j = 0; j < area_cnt; j++)
		{
			if (i == j) continue;
			if (area_list[i][j] == 1)
			{
				break_max_area = max(break_max_area, area_area[i] + area_area[j]);
			}
		}
	}
	cout << max_area_cnt << "\n" << max_area_size << "\n" << break_max_area;
}

 

아까 위에서 언급했듯이 모든 벽을 허물어보면서 탐색을 진행하는 방법도 물론 가능한 방법이다.

 

확실한건 아니지만 필자가 그 방법에다가 DFS를 이용했더니 메모리 사용량은 줄었지만 시간이 더 늘어지는 현상이 나타났다. 

 

구글링을 통해 알아보니 모든 벽을 허무는 방법은 아마 BFS를 이용해야 시간이 줄어드는 것 같은데... 이 부분은 다시 한번 짜봐야 알 것 같다.

 

어쨌든

굳