[BOJ2234] 성곽

[BOJ2234] 성곽

문제 링크

문제 설명

• 이 문제는 조금 특이하게 입력을 받는다. 배열판의 각 칸마다 숫자를 입력받는데, 서쪽에 벽이 있을 경우는 1을 더하고, 북쪽에 벽이 있을 경우는 2를 , 동쪽에 있을 땐 4, 남쪽에 벽이 있을 때는 8을 더하여 입력을 받는다. 예를 들어, 12를 입력받는 경우는 그 칸의 동쪽과 남쪽 방향으로 벽이 있다는 뜻이다.
• 배열판을 모두 입력을 받고 난 후, 이 성에 있는 방의 개수, 가장 넓은 방의 넓이와 하나의 벽을 제거하여 얻을 수 있는 가장 넓은 방의 크기 세가지를 구하는 문제이다.

코드 리뷰

• 먼저 입력받는 값을 0~15까지 나눠서 할 수도있지만, 값을 4번 반복하며 2로 나눈 나머지를 통해 벽이 있는지 없는지를 확인할 수 있다. 총 4비트이기때문에, 2로 네번 나눈 나머지를 통해 동서남북 갈 수 있는지 없는지를 확인한다.(0이면 벽이 없고 1이면 벽이 있음)
• 이 부분만 해결하고나면 나머지는 어렵지 않게 풀 수 있다. BFS 탐색을 하며, 한번 BFS가 끝날 때마다 방의 개수를 1개씩 늘려 방의 개수를 확인 할 수 있다.
• 각 방의 크기는 BFS를 한 번돌때 cnt를 통해 방의 크기를 센 후, 가장 큰 cnt를 찾으면 된다.
• 세번째 질문에 대한 답은 cnt를 한번 찾을때마다 벡터에 push_back을 하여 값을 가지고 있는다. 그 후, bfs를 새로 돌면서 현재 위치와 다음위치가 다른 방인 경우 벡터에 가지고 있던 두 값을 더하여 큰 값을 저장해나가면 된다.

#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
#include <utility>
using namespace std;
typedef pair<int, int> p;

typedef struct {
	int num;
	int room; // 방의 번호
}board_info;

board_info board[51][51];
vector <int> v;
queue <p> q;
int check[51][51];
int n, m;
int roomnum;
int cnt;
int sum_MAX;
int cnt_MAX;
int dc[4] = { 0,-1,0,1 };
int dr[4] = { -1,0,1,0 };

void bfs(int i, int j) {
	q.push(make_pair(i, j));
	while (!q.empty()) {
		int xnow = q.front().first;
		int ynow = q.front().second;
		board[xnow][ynow].room = roomnum;
		cnt++;
		q.pop();
		for (int k = 0; k < 4; k++) {
			if (board[xnow][ynow].num % 2 == 0 ) {
				int xnext = xnow + dc[k];
				int ynext = ynow + dr[k];
				if (board[xnext][ynext].room == 0) {
					q.push(make_pair(xnext, ynext));
					board[xnext][ynext].room = roomnum;
				}
			}
			board[xnow][ynow].num = board[xnow][ynow].num / 2;
		}
	}
}
void sum_BFS(int i, int j) {
	q.push(make_pair(i, j));
	while (!q.empty()) {
		int xnow = q.front().first;
		int ynow = q.front().second;
		check[xnow][ynow] = 1;
		q.pop();
		for (int k = 0; k < 4; k++) {
			int xnext = xnow + dc[k];
			int ynext = ynow + dr[k];
			if (xnext < 0 || xnext >= m || ynext < 0 || ynext >= n || check[xnext][ynext]!=0) continue;
			else if (board[xnow][ynow].room != board[xnext][ynext].room) {
				sum_MAX = max(sum_MAX, v[board[xnow][ynow].room - 1] + v[board[xnext][ynext].room - 1]);
			}
			q.push(make_pair(xnext, ynext));
			check[xnext][ynext] = 1;
		}
	}
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> n >> m;
	for (int i = 0; i < m; i++) {
		for (int j = 0; j < n; j++) {
			cin >> board[i][j].num;
		}
	}
	for (int i = 0; i < m; i++) {
		for (int j = 0; j < n; j++) {
			if (board[i][j].room == 0) {
				roomnum++;
				bfs(i, j);
				cnt_MAX = max(cnt_MAX, cnt);
				v.push_back(cnt);
				cnt = 0;
			}
		}
	}
	sum_BFS(0, 0);
	v.clear();
	cout << roomnum << '\n';
	cout << cnt_MAX << '\n';
	cout << sum_MAX << '\n';
	return 0;
}