[백준/c++] - 14502 연구소

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

14502번: 연구소

 

 

 

 

 

 

 

 

 DFS와 BFS모두 써야했던 문제이다. 문제에서 총 3개의 벽을 세우는 코드를 어떤 식으로 짜야할지 고민하다가 정답 코드를 참고했는데 대부분 DFS로 하였길래 DFS를 활용했다.

 

 

 

 

 

 

 

 

 

 

 벽을 세우는 위치를 어떻게 결정하지? 라는 생각을 가지고 문제를 보다가 맵의 크기가 최대 8 x 8인 것을 확인하고 '아 백트래킹 문제구나' 라는 것을 깨달았다. 그리고 그것을 DFS로 구현해서 빠르게 구현하는 것이 포인트인 문제라고 생각이 든다. 

 

 

 

 

 

 

 

#include <iostream>
#include <vector>
#include <queue>
#include <tuple>
#include <climits>
#include <stack>

using namespace std;

// BFS 문제, 백트래킹, 모두 확인해야함. 전체 칸의 최대 수가 3에서 8로 작다.

struct Pos {
	int X;
	int Y;
};

int frontX[4]{ 1, -1, 0, 0 };
int frontY[4]{ 0, 0, 1, -1 };

vector<vector<int>> map(8, vector<int>(8, 0));
vector<Pos> startPos;
vector<vector<int>> mapWall;

int N, M;
int ans = 0;

void input() {
	
	cin >> N >> M;

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			int val;
			cin >> val;
			
			map[i][j] = val;
			if (val == 2) {
				startPos.push_back(Pos{ j, i });
			}
		}
	}

	mapWall = map;
}

void checkSafe(vector<vector<int>> & afterSpread) {

	int safeCount = 0;

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			if (afterSpread[i][j] == 0)
				safeCount++;
		}
	}

	ans = max(ans, safeCount);

}




void bfs() {

	vector<vector<int>> afterSpread = mapWall; // 세이브

	queue<Pos>bfsQueue;

	for (Pos pos : startPos) { // 바이러스 시작지점이 여러개일 수 있음
		bfsQueue.push(pos);
	}

	while (bfsQueue.empty() == false) {

		Pos curPos = bfsQueue.front();
		bfsQueue.pop();

		for (int i = 0; i < 4; i++) {

			Pos nextPos{ curPos.X + frontX[i], curPos.Y + frontY[i] };

			// 맵 벗어난 경우
			if (nextPos.X >= M || nextPos.Y >= N || nextPos.X < 0 || nextPos.Y < 0) continue;

			// 방문 불가능한 경우
			if (afterSpread[nextPos.Y][nextPos. X] != 0) continue;


			// 발견
			afterSpread[nextPos.Y][nextPos.X] = 2;
			bfsQueue.push(nextPos);
		}

	}

	checkSafe(afterSpread);

}

// 세이프 지점 검사
void makeWall(int cnt) {

	if (cnt == 3) {
		bfs();
		return;
	}

	// 벽을 세워야함
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			if (mapWall[i][j] == 0) {
				// 벽을 세운다.
				mapWall[i][j] = 1;

				makeWall(cnt + 1);

				// 벽을 허문다. (dfs)
				mapWall[i][j] = 0;

			}

		}
	}

}



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

	cout << ans << endl;
}

 

 

 

 

 

 

 

 

 

 또 헷갈릴만하다고 생각이 들었던 부분은 맵 복사시점이다. 처음 원본 맵, 벽만 세운 맵, 바이러스가 모두 퍼진 후의 맵 이렇게 총 3개지 버전을 가지고 놀아야하는데 생각을 빠르게 하지 못하면 여기서도 삽질을 할 가능성이 크다고 본다. 나중에도 이런 문제를 만난다면 어떤 데이터를 보존하고 어떤 데이터를 언제 초기화할지 빠르게 판단할 수 있도록 해야할 필요가 있다.