[baekjoon 14502] 연구소 - 그래프탐색(BFS,DFS), 브루트포스

www.acmicpc.net/problem/14502

14502번: 연구소

기본적인 그래프 탐색에 벽을 쌓아야하는 경우를 생각해야하는 문제이다.

처음에 문제를 읽고 무작위 벽 3개를 어떤 로직을 통해 세워야할까, 고민을 하다가 입력값의 최대 배열 크기가 8x8 인것을 보고 브루트포스로 모든 경우를 탐색해보면 되겠다고 생각을 했다.

 

벽을 세우는 케이스는 크게 두가지 인 것 같다.

1. 그래프를 입력받을 때 벽도 없고, 바이러스도 없는 x,y 좌표값을 따로 vector에 보관해두고 이 벡터에서 3가지 경우를 조합해서 벽을 쌓아 탐색하는 경우

2. 백트래킹(재귀)을 이용해서 조합 알고리즘으로 3개의 벽을 쌓아 탐색하는 경우

 

나의 경우 1번을 통해 3중for문을 통해 벽을 세웠다.

 

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

using namespace std;

int N, M, num, wall, check[9][9], range[9][9], Max, disX[4] = { 1,-1,0,0 }, disY[4] = { 0, 0, 1, -1 };
vector < pair<int, int>> virus;
vector < pair<int, int>> noWall;

void VirusBFS(int x, int y) {
	queue<pair<int, int>> q;
	q.push(make_pair(x, y));

	while (!q.empty()) {
		int tempX = q.front().first;
		int tempY = q.front().second;
		check[tempX][tempY] = 1;
		q.pop();

		for (int i = 0; i < 4; i++) {
			int X = tempX + disX[i];
			int Y = tempY + disY[i];
			if (X >= 0 && X < N && Y >= 0 && Y < M) {
				if (!check[X][Y] && range[X][Y] == 0) {
					check[X][Y] = 1;
					q.push(make_pair(X, Y));
				}
			}
		}
	}
}

void clearCheck() {
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			check[i][j] = 0;
		}
	}
}

int main() {
	ios::sync_with_stdio(false); cin.tie(NULL);
	cin >> N >> M;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			cin >> num;
			range[i][j] = num;
			if (num == 0) {
				noWall.push_back(make_pair(i, j));
			}
			else if (num == 2)
				virus.push_back(make_pair(i, j));
		}
	}
	int noWallSize = noWall.size();
	for (int i = 0; i < noWallSize-2; i++) {
		pair<int, int> temp1 = noWall[i];
		range[temp1.first][temp1.second] = 1;
		// 1차 벽 세우기
		for (int j = i + 1; j < noWallSize-1; j++) {
			pair<int, int> temp2 = noWall[j];
			range[temp2.first][temp2.second] = 1;
			// 2차 벽세우기
			for (int k = j + 1; k < noWallSize; k++) {
				pair<int, int> temp3 = noWall[k];
				range[temp3.first][temp3.second] = 1;
				// 3차 벽세우기
				for (int vir = 0; vir < virus.size(); vir++) {
					VirusBFS(virus[vir].first, virus[vir].second);
					// 벽 세우고 Virus 퍼진 상태
				}
				int cnt = 0;
				for (int Xx = 0; Xx < N; Xx++) {
					for (int Yy = 0; Yy < M; Yy++) {
						if (range[Xx][Yy] == 0 && !check[Xx][Yy]){
							cnt++;
							Max = max(Max, cnt);
						}
					}
				}
				clearCheck();
				range[temp3.first][temp3.second] = 0;
				//계속 세번째 벽 위치만 바뀌므로 세번째만 해제해준다.
			}
			range[temp2.first][temp2.second] = 0;
			// 세번째 모두 돌면 두번째 벽 바꿔줘야하므로 해제해준다.
		}
		range[temp1.first][temp1.second] = 0;
		// 첫번째 벽 해제
	}

	cout << Max;
}

3중 for문을 시작하는 부분부터 0만 저장되어 있는 좌표에서 하나씩 꺼내서 벽을 세워준다.

그리고 각자의 for문이 끝나면 원래의 입력받은 그래프로 바꾸기 위해서 0으로 다시 바꿔준다.

3중 for문으로 벽을 다 세운 다음엔 virus 벡터에서 2인 케이스를 시작점으로 그래프탐색을 해준다.

나는 바이러스가 퍼진 경우를 지도에 직접 바꾸기보다 check (방문여부 2차원 배열)을 바꿔줌으로써 나중에 안전영역의 갯수를 셀때 구별을 해주었다.

그렇게 바이러스가 퍼질 수 있는 탐색을 모두 마친 후, 0이면서 방문하지 않은 위치의 갯수를 세서 최댓값을 max에 저장 후 출력해주었다.

 

- 피드백

1. for문을 많이 쓰다 보니까 for문 안의 변수를 다른 for문의 변수로 잘못 쓴 경우가 빈번했다.

이 경우 for문의 변수가 제대로 실행되지 않아서 runtime error가 발생했다. 

 

2. 문제를 제대로 읽자. -> 처음에 connected component처럼 0이 이어져있는 최대의 영역을 구하는 건 줄 알고 0을 구하기 위해서 BFS를 한번 더 탐색했고, 답도 틀리게 나왔다.

이 문제에서는 그냥 최종적으로 탐색 후 0의 갯수만 세면 되는 것이었다.