BOJ_14502_연구소(C++) [DFS and BFS]

PS 백준 소스 코드 모음 : https://github.com/kgw4073/Problem-Solving

---

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

14502번: 연구소

 나는 이 문제를 DFS와 BFS로 풀었으며 그 외에 다른 방식은 딱히 떠오르지 않았다.

 

 이 문제를 풀 때 가장 중요한 것은 당연히 DFS와 BFS 구현 방법인데, 이 중에서도 간단한 백트래킹(Back-tracking)이 필요하다. 백트래킹은 트리를 만들어 나가며 탐색하는 과정에서 필요 없는 부분은 탐색하지 않는다는 것인데 이 것은 N과 M 시리즈로 연습하길 추천한다. 꼭! (백준 N과 M 문제집 https://www.acmicpc.net/workbook/view/2052)

문제집: N과 M (baekjoon)

여기서 잠깐!

 

 대부분의 사람들은 윈도우 환경에서 Microsoft Visual Studio (MSVC 컴파일러)를 사용할 것이다. 근데 여기서 디버그 모드로 돌리면 다음 테스트 케이스에서 꽤 오랜 시간이 걸릴 것이다. (대략 4-5초?)

8 8 2 0 0 0 0 0 0 2 2 0 0 0 0 0 0 2 2 0 0 0 0 0 0 2 2 0 0 0 0 0 0 2 2 0 0 0 0 0 0 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

 그런데 이 문제의 시간 제한은 2초이다. 아 그럼 여기서 시간을 줄여야겠구나.. 라는 한숨이 나올 것이다. 나도 그랬다. 하지만 아무리 생각해봐도 시간 초과가 날 문제가 아닌 것 같았다.

 

N, M이 최대 8이므로 칸의 최대 개수는 64개이고 이 중에 빈 칸이 될 수 있는 최대 개수는 63개이다. 

 

 63개 중 3개를 선택해서 벽을 세워야 하는데 63 x 62 x 61 / 6 = 39,711 이고 바이러스의 최대 개수는 10개에 각 바이러스마다 64칸 씩 bfs로 탐색한다고 하더라도 39711 * 10 * 64 = 25,415,040 이다. (아 물론 이건 절대 정확한 값은 아니다 대강 대강 연산의 수를 계산하기 위해 설정한 것이다.) PS에서 대략적으로 컴퓨터가 1초에 10^8번 (1억 번)의 연산을 한다는 것을 고려했을 때 충분히 범위 내에 들어온다. 다음은 리눅스에서 g++로 컴파일한 후 실행한 결과이다. 다른 옵션은 주지 않았다.

 

<그림 1 : Linux에서 g++로 돌린 결과>

 

 그러니까 이제 MSVC에서 디버그 모드로 돌리고 나서 나처럼 쪼는 일은 없도록 하자. 정 미덥지 못하면 Ubuntu를 깔아서 써보거나 Release 모드로 바꾸고 실행 시간을 측정해보자. (물론 이게 정확한 실행 시간인지는 모르겠으나 어느 정도는 맞는 것 같다.)

<그림 2 : MSVC에서 Release모드로 돌린 결과>

 

---

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

using namespace std;

int n, m;

// 연구소 상태 맵
int map[8][8];

// virus는 virus가 있는 좌표를 담음
vector<pair<int, int>> virus;

// clean는 오염되지 않은 좌표를 담음
vector<pair<int, int>> clean;

// wall은 새로 새울 벽이다(기존에 세워진 벽 아님)
vector<pair<int, int>> wall;

// 방향 이동
int dy[] = { 0, 1, 0, -1 };
int dx[] = { 1, 0, -1, 0 };

// safeArea는 아직 바이러스가 퍼지지 않은 상태에서 오염되지 않은 곳의 수
int safeArea = 0;
// 가장 큰 safeArea를 저장
int maxSafeArea = 0;

void bfs(int map[][8], int safeArea) {
	// virus가 있는 곳마다 전부 bfs를 시행
	for (pair<int, int> vir : virus) {
		queue<pair<int, int>> q;
		int y = vir.first;
		int x = vir.second;
		q.push({ y, x });
		while (!q.empty()) {
			y = q.front().first;
			x = q.front().second;
			q.pop();
			for (int dir = 0; dir < 4; dir++) {
				int ny = y + dy[dir], nx = x + dx[dir];
				// 해당 맵에 벽이 있거나 바이러스가 있거나 인덱스를 벗어나면 바이러스 안 퍼짐
				if (map[ny][nx] || ny < 0 || ny >= n || nx < 0 || nx >= m) {
					continue;
				}
				// 바이러스 퍼짐
				map[ny][nx] = 2;
				q.push({ ny, nx });
				safeArea--;
			}
		}
	}
	// 바이러스가 모두 퍼진 상태에서 maxSafeArea와 비교
	maxSafeArea = max(maxSafeArea, safeArea);
	return;
}

// 오염되지 않은 곳에 벽을 세움 
void dfs(int idx, int depth) {
	// 세 개를 세웠으면 이제 바이러스가 퍼져야 함.
	if (depth == 3) {
		// 다른 상황을 탐색해야 하므로 map을 바이러스가 퍼지게 냅두면 안됨
		// temp에다가 복사해서 넘기자!
		int temp[8][8];
		memcpy(temp, map, sizeof(temp));
		// safeArea - 3을 넘긴 이유는 벽을 세 개 세웠으니까
		bfs(temp, safeArea - 3);
		return;
	}

	// clean한 곳 중에 세 곳을 고르는 오름차순 백트래킹
	for (int i = idx + 1; i < clean.size(); i++) {
		wall.push_back(clean[i]);
		map[clean[i].first][clean[i].second] = 1;
		dfs(i, depth + 1);
		map[clean[i].first][clean[i].second] = 0;
		wall.pop_back();
	}
}

int main() {
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> map[i][j];
			// 오염되지 않은 곳이므로 safeArea 증가, clean vector에 좌표 넣음
			if (map[i][j] == 0) {
				clean.emplace_back(i, j);
				safeArea++;
			}
			// 바이러스 있으면 virus vector에 넣음
			else if (map[i][j] == 2) {
				virus.emplace_back(i, j);
			}
		}
	}
	// dfs로 벽 세 개 세움
	dfs(-1, 0);
	cout << maxSafeArea;
}