[Algorithm][C++] BOJ 2234 성곽

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

2234번: 성곽

 

풀이 핵심

1. BloodFill 문제로 BFS를 이용해 구현

2. 값이 모두 true인 flag[4] 생성, 벽으로 막힌 곳 찾기 위해 다음과 같이 구현, false로 표시 된 방향으로는 탐색 하지 않음.

bool flag[4] = { 1,1,1,1 };
int tmp = map[cur.r][cur.c];
for (int i = 0; i < 4; i++) {
  if (tmp % 2) {
  	flag[i] = false;
  }
  tmp /= 2;
}

3. check배열에 다음과 같이 표시

4. 각각의 방의 개수를 room 배열에 다음과 같이 저장 (마지막 방 번호 = 이 성의 방의 개수, 가장 넓은 방 탐색)

5. 방 번호를 입력한 check 배열 주변 탐색 (인접한 방 번호 nearing 배열로 기록)

6. 하나의 벽을 제거하고 가장 넓은 방 탐색 

 

코드

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <queue>
using namespace std;

int R, C;
int map[50][50];
int check[50][50];
int room[2501];
bool nearing[2501][2501];
int rn;
struct pos { int r, c; };
const int dr[] = { 0,-1,0,1 };
const int dc[] = { -1,0,1,0 };

void InputData();
void BloodFill(int r, int c);
void Solve();

int main() {
	InputData();
	Solve();
	return 0;
}

void InputData() {
	scanf("%d %d", &C, &R);
	for (int i = 0; i < R; i++) {
		for (int j = 0; j < C; j++) {
			scanf("%d", &map[i][j]);
		}
	}
}

void BloodFill(int r, int c) {
	queue<pos> q;
	int count = 0;
	++rn;
	q.push({ r,c });
	check[r][c] = rn;
	count++;
	while (!q.empty()) {
		pos cur = q.front();
		q.pop();
		bool flag[4] = { 1,1,1,1 };
		int tmp = map[cur.r][cur.c];
		for (int i = 0; i < 4; i++) {
			if (tmp % 2) {
				flag[i] = false;
			}
			tmp /= 2;
		}
		for (int i = 0; i < 4; i++) {
			if (flag[i]) {
				int nr = cur.r + dr[i];
				int nc = cur.c + dc[i];
				if (check[nr][nc]) continue;
				q.push({ nr,nc });
				check[nr][nc] = rn;
				count++;
			}
		}
	}
	room[rn] = count;
}

void Solve() {
	for (int i = 0; i < R; i++) {
		for (int j = 0; j < C; j++) {
			if (!check[i][j]) {
				BloodFill(i, j);
			}
		}
	}
	int max = 0;
	for (int i = 1; i <= rn; i++) {
		if (room[i] > max) max = room[i];
	}
	
	for (int i = 1; i <= rn; i++) {
		for (int r = 0; r < R; r++) {
			for (int c = 0; c < C; c++) {
				if (check[r][c] != i) continue;
				for (int dir = 0; dir < 4; dir++) {
					int nr = r + dr[dir];
					int nc = c + dc[dir];
					if (nr < 0 || nr >= R || nc < 0 || nc >= C) continue;
					if (check[nr][nc] != i) {
						nearing[i][check[nr][nc]] = true;
					}
				}
			}
		}
	}
	int plus_max = 0;
	for (int i = 1; i <= rn; i++) {
		for (int j = 1; j <= rn; j++) {
			if (nearing[i][j]) {
				int tmp_max = room[i] + room[j];
				if (plus_max < tmp_max) plus_max = tmp_max;
			}
		}
	}
	printf("%d\n%d\n%d", rn, max, plus_max);
}

 

아쉬운 점

1. 계속 OutOfBound 에러가 나와서 당황했다. 방의 최대 개수가 50개라고 문제를 잘 못 읽어 room[51], nearing[51][51]로 배열 크기를 선언했기 때문이었다. 문제를 다시 읽어보니 가로 최대 50 세로 최대 50 이었다. 그래서 최대 방 생성 개수는 2500이므로 room[2501], nearing[2501][2501]로 수정했다.