[백준] 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 <queue>

#define	WEST	0
#define	NORTH	1
#define	EAST	2
#define	SOUTH	3

using namespace std;

struct pos
{
	int r;
	int c;

	void init(int r, int c)
	{
		this->r = r;
		this->c = c;
	}
};

int N;
int M;
bool map[51][51][4];			// map[i][j][k]는 (i, j) 칸의 k 방향에 벽이 있는지
int room[51][51];			// room[i][j]는 (i, j) 칸이 몇 번 방에 속하는지
int num;				// 방의 번호 (1부터 시작) -> 방의 개수
int max_size;				// 가장 넓은 방의 크기
vector<int> room_size;			// room_size[i]는 i번 방의 크기
vector< vector<bool> > adjacent_room;	// adjacent_room[i][j]는 i번 방과 j번 방이 인접한지

// (r, c)칸의 각 방향에 벽이 있는지 확인함
void check_wall(int r, int c, int wall)
{
	if (wall & 0x01)
		map[r][c][WEST] = true;
	if (wall & 0x02)
		map[r][c][NORTH] = true;
	if (wall & 0x04)
		map[r][c][EAST] = true;
	if (wall & 0x08)
		map[r][c][SOUTH] = true;
}

// 범위 안인지 확인함
bool in_range(pos p)
{
	if (p.r < 0 || p.r >= M || p.c < 0 || p.c >= N)
		return false;
	return true;
}

// (r, c)가 속하는 방을 찾음
void bfs(int r, int c)
{
	queue<pos> q;
	pos curr, next;
	int dr[] = {0, -1, 0, 1};	// W-N-E-S
	int dc[] = {-1, 0, 1, 0};	// W-N-E-S
	int i, cnt = 0;			// cnt는 방의 크기

	curr.init(r, c);
	q.push(curr);
	room[r][c] = ++num;	
	adjacent_room.push_back(vector<bool> (num, false));
	while (!q.empty())
	{
		cnt++;
		curr = q.front();
		q.pop();
		for (i = 0; i < 4; i++)
		{
			next.init(curr.r + dr[i], curr.c + dc[i]);
			if (!in_range(next))
				continue;
			if (map[curr.r][curr.c][i])
			{
      				// 인접한 방의 번호 확인
				if (room[next.r][next.c] && room[next.r][next.c] != num)
					adjacent_room[num][room[next.r][next.c]] = true;
				continue;
			}
			if (room[next.r][next.c])
				continue;
			q.push(next);
			room[next.r][next.c] = num;
		}
	}
        // num번 방의 크기 저장
	room_size.push_back(cnt);
    	// 방 크기의 최댓값 갱신
	max_size = max(max_size, cnt);
}

// 모든 방을 찾음
void find_room()
{
	int i, j;

	// 0번 방은 없으므로 크기를 1로 초기화하여 1번 방부터 저장할 수 있도록 함
	room_size.resize(1);
	adjacent_room.resize(1);
	for (i = 0; i < M; i++)
	{
		for (j = 0; j < N; j++)
		{
        		// 아직 확인되지 않은 칸이면 탐색
			if (!room[i][j])
				bfs(i, j);
		}
	}
}

// 하나의 벽을 제거하여 얻을 수 있는 가장 넓은 방의 크기를 구함
int destroy_wall()
{
	int i, j, sum, res = 0;

	for (i = 1; i <= num; i++)
	{
		for (j = 1; j < adjacent_room[i].size(); j++)
		{
        		// 인접한 방과 합쳤을 때의 크기를 구하여 최댓값 갱신
			if (adjacent_room[i][j])
				res = max(res, room_size[i] + room_size[j]);
		}
	}
	return res;
}

int main()
{
	int i, j, k, wall;

	cin >> N >> M;
	for (i = 0; i < M; i++)
	{
		for (j = 0; j < N; j++)
		{
			cin >> wall;
			check_wall(i, j, wall);
		}
	}
	find_room();
	cout << num << endl;
	cout << max_size << endl;
	cout << destroy_wall() << endl;
	return 0;
}

 

링크

2234번: 성곽

inbdni/Baekjoon