[BOJ - 2234] 성곽

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

2234번: 성곽

 

 

구현이 빡센 BFS 문제를 풀어보고 싶어 문제집을 찾던 도중 제일 난이도가 쉬워보이는 문제를 찾았다.

 

그냥 BFS로 빡구현했고 내가 문제를 푸는데 집중한 부분은 처음 입력받은 정수를 이진수로 표현해서 구조체 배열에 저장하는 것이었다.

 

그리고 아마 하나의 벽을 제거해서 얻을 수 있는 가장 넓은 방의 크기를 구하는 것에서 살짝 막혔는데

 

처음에 BFS를 돌릴 때 벽을 제거하기 전 방들을 넘버링해서 구분하고 이를 이용해 인접한 것들 끼리 비교해 최댓값을 구했다.

 

-풀이 방법

위에 설명했으니 생략~

(궁금한점 있으면 댓글 남겨주세요!)

 

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

struct MAP {
	int direction[4];
};
struct POINT {
	int y, x;
};
int n, m;
const int dy[] = { 0,-1,0,1 };
const int dx[] = { -1,0,1,0 };
vector<vector<MAP>> vec;
MAP room[51][51];
int map[51][51];
int visited[51][51];
int room_num[2501];
queue<POINT> q;

bool cmp(int a, int b) {
	return a > b;
}

MAP div(int num) {
	MAP temp;
	temp.direction[0] = (num % 2);
	num /= 2;
	temp.direction[1] = (num % 2);
	num /= 2;
	temp.direction[2] = (num % 2);
	num /= 2;
	temp.direction[3] = (num % 2);
	return temp;
}

int main(void) {

	scanf("%d %d", &n, &m);

	for (int y = 0; y < m; y++) {
		for (int x = 0, temp; x < n; x++) {
			scanf("%d", &temp);
			map[y][x] = temp;
			room[y][x] = div(temp);
		}
	}

	int room_cnt = 1;

	for (int y = 0; y < m; y++) {
		for (int x = 0; x < n; x++) {
			if (visited[y][x] == 0) {
				q.push({ y,x });
				visited[y][x] = room_cnt;
				room_num[room_cnt] += 1;

				while (!q.empty()) {
					POINT cur = q.front();
					q.pop();

					for (int dir = 0; dir < 4; dir++) {
						POINT next;
						next.y = cur.y + dy[dir];
						next.x = cur.x + dx[dir];

						if (next.y < 0 || next.y >= m || next.x < 0 || next.x >= n || visited[next.y][next.x]) continue;
						if (room[cur.y][cur.x].direction[dir] == 0) {
							visited[next.y][next.x] = room_cnt;
							room_num[room_cnt] += 1;
							q.push(next);
						}
					}
				}
				room_cnt += 1;
			}
		}
	}
	
	//room_cnt-1이 1번 답
	//room_num[0]이 2번 답
	//sort(room_num, room_num + room_cnt, cmp);
	int first = room_cnt - 1;

	int visit[51][51] = { 0, };
	queue<POINT> que;
	int third = 0;

	for (int y = 0; y < m; y++) {
		for (int x = 0; x < n; x++) {
			if (visit[y][x] == 0) {
				que.push({ y,x });
				visit[y][x] = 1;

				while (!que.empty()) {
					POINT cur = que.front();
					que.pop();

					for (int dir = 0; dir < 4; dir++) {
						POINT next;
						next.y = cur.y + dy[dir];
						next.x = cur.x + dx[dir];

						if (next.y < 0 || next.y >= m || next.x < 0 || next.x >= n || visit[next.y][next.x]) continue;
						if (visited[cur.y][cur.x] != visited[next.y][next.x]) {
							third = max(third, room_num[visited[cur.y][cur.x]] + room_num[visited[next.y][next.x]]);
						}
						else if (visited[cur.y][cur.x] == visited[next.y][next.x]) {
							visit[next.y][next.x] = 1;
							que.push(next);
						}
					}
				}
			}
		}
	}

	sort(room_num, room_num + room_cnt, cmp);
	int second = room_num[0];

	cout << first << "\n" << second << "\n" << third;
	
	getchar();
	getchar();

	return 0;
}