[백준 C++] 14502번: 연구소

1. 문제

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

14502번: 연구소

 

2. 알고리즘 분류

• 구현
• 그래프 이론
• 프루트포스 알고리즘
• 그래프 탐색
• 너비 우선 탐색

 

3. 소스 코드

#include <iostream>
#include <vector>
#include <cstring>
#include <queue>
#include <algorithm>
using namespace std;

int N, M, max_safetyArea = 0;
int map[10][10];
int tmp_map[10][10];
int dy[] = { -1, 0, 1, 0 };
int dx[] = { 0, 1, 0, -1 };
vector<pair<int, int>> virus;
vector<pair<int, int>> walls;

// 바이러스가 퍼져나가는 것을 구현한 BFS
void bfs() {
	// 현재 맵을 임시 맵에 복사
	memcpy(tmp_map, map, sizeof(map));

	// 바이러스 위치를 큐에 저장
	queue<pair<int, int>> q;
	for (int i = 0; i < virus.size(); i++)
		q.push({ virus[i].first, virus[i].second });

	// 퍼져나갈 공간이 없을 때까지 BFS 동작
	while (!q.empty()) {

		// 현재 위치
		int cur_y = q.front().first;
		int cur_x = q.front().second;
		q.pop();

		// 상, 하, 좌, 우 방향으로 다음 위치로 이동
		for (int i = 0; i < 4; i++) {
			int next_y = cur_y + dy[i];
			int next_x = cur_x + dx[i];

			// 맵 바깥으로 벗어날 경우 Skip
			if (next_y < 0 || next_y >= N || next_x < 0 || next_x >= M) continue;	// 맵 바깥으로 벗어날 경우 skip
			if (tmp_map[next_y][next_x] != 0) continue;		// 다음 위치가 빈 칸이 아닐 경우 skip

			tmp_map[next_y][next_x] = 2;	// 다음 위치에 바이러스 전파
			q.push({ next_y, next_x });		// 다음 위치의 값을 큐에 저장
		}
	}
}

// 안전 영역의 크기를 구해주는 함수
int get_safetyArea() {
	int ret = 0;

	// 모든 맵을 탐색하면서 빈 칸일 경우 ret에 1씩 더하기
	for (int y = 0; y < N; y++)
		for (int x = 0; x < M; x++)
			if (tmp_map[y][x] == 0) ret++;

	return ret;
}

// 벽을 세울 3군데 선정하는 DFS 함수
void dfs(int lv) {

	// 벽의 위치를 3군데 선정했을 경우 반환
	if (lv == 3) {
		bfs();	// 바이러스 전파
		int safetyArea = get_safetyArea();	// 안전 영역의 크기 구하기
		max_safetyArea = max(max_safetyArea, safetyArea);	// 최대 안전 영역의 크기 구하기
		return;
	}

	// 모든 맵을 탐색하면서 벽을 세우기
	for (int y = 0; y < N; y++) {
		for (int x = 0; x < M; x++) {
			if (map[y][x] != 0) continue;	// 해당 위치가 빈칸이 아닐 경우 skip

			map[y][x] = 1;		// 해당 위치에 벽 세우기
			dfs(lv + 1);		// 다시 벽을 세우는 DFS 함수로 재귀
			map[y][x] = 0;		// 재귀 끝난 후, 다시 해당 위치에 벽을 치우기
		}
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	// 입력
	cin >> N >> M;

	for (int y = 0; y < N; y++)	{
		for (int x = 0; x < M; x++)	{
			cin >> map[y][x];
			if (map[y][x] == 2) virus.push_back({ y, x });
		}
	}

	// 벽을 3군데 세우는 함수
	dfs(0);

	// 출력
	cout << max_safetyArea;

	return 0;
}

 

4.  유용한 문법 및 알고리즘

4-1)  DFS 알고리즘(깊이 우선 탐색, 벽을 세울 위치 3군데 선정)

void dfs(int lv) {

	// 벽의 위치를 3군데 선정했을 경우 반환
	if (lv == 3) {
		bfs();	// 바이러스 전파
		int safetyArea = get_safetyArea();	// 안전 영역의 크기 구하기
		max_safetyArea = max(max_safetyArea, safetyArea);	// 최대 안전 영역의 크기 구하기
		return;
	}

	// 모든 맵을 탐색하면서 벽을 세우기
	for (int y = 0; y < N; y++) {
		for (int x = 0; x < M; x++) {
			if (map[y][x] != 0) continue;	// 해당 위치가 빈칸이 아닐 경우 skip

			map[y][x] = 1;		// 해당 위치에 벽 세우기
			dfs(lv + 1);		// 다시 벽을 세우는 DFS 함수로 재귀
			map[y][x] = 0;		// 재귀 끝난 후, 다시 해당 위치에 벽을 치우기
		}
	}
}

 

4-2) BFS 알고리즘(너비 우선 탐색, 바이러스 전파 구현)

// 바이러스가 퍼져나가는 것을 구현한 BFS
void bfs() {
	// 현재 맵을 임시 맵에 복사
	memcpy(tmp_map, map, sizeof(map));

	// 바이러스 위치를 큐에 저장
	queue<pair<int, int>> q;
	for (int i = 0; i < virus.size(); i++)
		q.push({ virus[i].first, virus[i].second });

	// 퍼져나갈 공간이 없을 때까지 BFS 동작
	while (!q.empty()) {

		// 현재 위치
		int cur_y = q.front().first;
		int cur_x = q.front().second;
		q.pop();

		// 상, 하, 좌, 우 방향으로 다음 위치로 이동
		for (int i = 0; i < 4; i++) {
			int next_y = cur_y + dy[i];
			int next_x = cur_x + dx[i];

			// 맵 바깥으로 벗어날 경우 Skip
			if (next_y < 0 || next_y >= N || next_x < 0 || next_x >= M) continue;	// 맵 바깥으로 벗어날 경우 skip
			if (tmp_map[next_y][next_x] != 0) continue;		// 다음 위치가 빈 칸이 아닐 경우 skip

			tmp_map[next_y][next_x] = 2;	// 다음 위치에 바이러스 전파
			q.push({ next_y, next_x });		// 다음 위치의 값을 큐에 저장
		}
	}
}