(cpp) Baekjoon 14502번 문제 ‘연구소’ - 구현, 그래프이론, 브루트포스, 그래프탐색, 너비우선탐색

19 Feb 2023 on Programming Languages

Baekjoon 14502번 문제 ‘연구소’ - 구현, 그래프이론, 브루트포스, 그래프탐색, 너비우선탐색

---

문제

예제입력2에 대한 문제풀이

1. 벽 3개를 세우는 경우는 브루트포스로 경우의 수를 모두 고려해야 한다.

2. 벽을 세울 때마다 감염 시뮬레이션 실행한다.

3. 감염된 상태에서 안전영역 구한다. 이 때 map의 0갯수 구하면 됨.

4. 매 case별로 안전영역 크기 구하고 최대값으로 계속해서 갱신한다.

코드

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
using namespace std;

int n, m, map[10][10], map_origin[10][10];
int r_pos[4] = { 1,-1,0,0 };
int c_pos[4] = { 0,0,1,-1 };
int virus[64][2];


void dfs(int p, int q) {
	for (int i = 0; i < 4; i++) {
		int next_p = p + r_pos[i];
		int next_q = q + c_pos[i];
		if (next_p > 0 && next_p <= n && next_q > 0 && next_q <= m && map[next_p][next_q] == 0) {
			map[next_p][next_q] = 2;
			dfs(next_p, next_q);
		}
	}
	return;
}


int main() {
	cin >> n >> m;
	int ans = 0;
	int num = 0;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			cin >> map[i][j];
			map_origin[i][j] = map[i][j];
			if (map[i][j] == 2) {
				virus[num][0] = i;
				virus[num][1] = j;
				num++;
			}
		}
	}



	int n1, m1, n2, m2, n3, m3;
	for (int i = 0; i < n * m; i++) {
		n1 = (i / m) + 1;
		m1 = (i % m) +1;

		if (map[n1][m1] == 0)
		{
			for (int j = i + 1; j < n * m; j++) {
				n2 = (j / m) + 1;
				m2 = (j % m) + 1;
				if (map[n2][m2] == 0)
				{
					for (int k = j + 1; k < n * m; k++) {
						n3 = (k / m) + 1;
						m3 = (k % m) + 1;
						if (map[n3][m3] == 0) {
							map[n1][m1] = 1;
							map[n2][m2] = 1;
							map[n3][m3] = 1;

							//벽 세운 후 감염시키기
							for (int p = 0; p <num; p++) {
								dfs(virus[p][0], virus[p][1]);
							}

							//감염 후 map에서 0갯수 세기
							int cnt = 0;
							for (int r = 1; r <= n; r++) {
								for (int c = 1; c <= m; c++) {
									if (map[r][c] == 0) {
										cnt++;
									}
								}
							}
							if (ans < cnt) {
								ans = cnt;
							}

							for (int u = 1; u <= n; u++) {
								for (int v = 1; v <= m; v++) {
									map[u][v] = map_origin[u][v];
								}
							}
						}
					}
				}
			}
		}
	}
	printf("%d", ans);
	return 0;
}

• 문제를 오히려 너무 어렵게 생각했었다. 시뮬레이션 map생성해야 함.
• 안전영역의 정의를 연속된 0의 범위가 최대인 것으로 잘못 생각했다. 단지 map전체에서의 0의 갯수만 구하면 됨.
• 벽 3개를 세우는 경우의 수를 삼중 for문으로 구현하는 idea와 이 때, index를 (행,열) 형태로 전환하는 것이 어려웠다.