백준 17141 c++ "연구소 2" -PlusUltraCode-

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

 

[필자 사고]

백트래킹, 조합, BFS 다 잘 설계를 했다.

다만 한가지 문제 였던게 BFS에서 dist라는 새로운 2차원 배열을 이용하여 거리계산만 담는 과정이 빼먹었다.

초기 값을 -1로 초기화를 하여 값이 변경됨을 기준으로 방문처리를 하면 좋은 방식일거 같다.

기존에는 arr[sero][garo] =2 인 경우도 접근을 못하게 했는데 이게 문제였떤거 같다.

위 풀이 방식 장기기억으로 바꾸자.

[코드 해설]

문제 개요

• N×N 크기의 연구소 격자에서 바이러스가 놓일 수 있는 위치(값=2)가 여러 개 주어진다.
• 이 중 M개를 선택해 동시에 퍼뜨릴 때, 모든 빈 칸(0)을 바이러스가 덮는 데 걸리는 최소 시간을 구하는 문제다.
• 벽(1)은 통과할 수 없다.
• 퍼지지 못하는 경우에는 -1을 출력한다.

---

핵심 아이디어

1. 조합(Backtracking)
   • 바이러스 후보 좌표(point)에서 M개를 고른다.
   • 모든 조합에 대해 BFS를 실행해 결과 시간을 구한다.
2. 다중 시작점 BFS
   • 선택된 M개 좌표를 동시에 시작점으로 큐에 넣는다.
   • 4방향으로 확산하면서 최단 시간(dist)을 기록한다.
   • 모든 빈 칸(0)에 도달 가능한지 확인하고, 도달한다면 그 중 최대 시간을 반환한다.
3. 최소값 갱신
   • 모든 조합에 대해 계산한 값 중 최소 시간을 정답으로 선택한다.
   • 단, 어떤 경우에도 퍼지지 못하면 -1을 출력한다.

---

주요 함수 해설

Input

• 입력을 받아 격자를 초기화한다.
• 값이 2인 칸은 바이러스 후보이므로 point 벡터에 저장한다.
• arr에서는 해당 칸을 0으로 바꿔 빈 칸처럼 처리한다.

isInside

• 좌표가 연구소 격자 내부에 있는지 판별하는 보조 함수.

BFS

• 선택된 바이러스 M개 좌표에서 동시에 시작하는 BFS 수행.
• dist 배열을 이용해 방문 여부 및 시간을 기록한다.
• 빈 칸이 모두 도달 가능하면 최댓값(=최소 소요 시간)을 반환한다.
• 도달하지 못한 빈 칸이 있으면 -1을 반환한다.

Back_Tracking

• point 배열에서 M개의 좌표를 조합으로 선택한다.
• M개를 모두 고르면 BFS를 수행해 결과를 저장한다.
• 재귀적으로 모든 조합을 탐색한다.

Game_Start

• Back_Tracking을 시작하고 모든 결과를 수집한다.
• BFS 결과 중 -1이 아닌 값만 대상으로 최소값을 찾는다.
• 가능한 경우 최소 시간을 출력, 아니면 -1을 출력한다.

main

• Input → Game_Start 순으로 실행.

 

[소스 코드]

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

typedef pair<int, int> Node;
struct queueNode {
	int sero;
	int garo;
	int count;
};

int dy[4] = { 0,-1,0,1 };
int dx[4] = { 1,0,-1,0 };

int N, M;
vector<vector<int>> arr; 
vector<Node> point;
int resultMinTime = 987654321;
vector<bool> idxVisited;
vector<Node> selectedPoint;
vector<int> result;
void Input() {
	cin >> N >> M;
	arr.assign(N, vector<int>(N, 0));

	for (int i = 0; i < N; i++) {
		for (int k = 0; k < N; k++) {
			cin >> arr[i][k];

			if (arr[i][k] == 2) {
				point.push_back({ i,k });
				arr[i][k] = 0;
			}
		}
	}
}

bool isInside(int sero, int garo) {
	if (sero >= 0 && sero < N && garo >= 0 && garo < N)return true;
	return false;
}

int BFS() {
	vector<vector<int>> dist(N, vector<int>(N, -1));
	queue<Node> q;

	for (auto& p : selectedPoint) {
		dist[p.first][p.second] = 0;
		q.push(p);
	}

	while (!q.empty()) {
		auto [y, x] = q.front(); q.pop();
		for (int d = 0; d < 4; ++d) {
			int ny = y + dy[d], nx = x + dx[d];
			if (!isInside(ny, nx)) continue;
			if (arr[ny][nx] == 1) continue;        // 벽만 막기
			if (dist[ny][nx] != -1) continue;
			dist[ny][nx] = dist[y][x] + 1;
			q.push({ ny, nx });
		}
	}

	int maxT = 0;
	for (int i = 0; i < N; ++i) {
		for (int k = 0; k < N; ++k) {
			if (arr[i][k] == 0) {                  // 빈 칸만 평가
				if (dist[i][k] == -1) return -1;   // 못 퍼진 빈 칸 존재
				maxT = max(maxT, dist[i][k]);
			}
		}
	}
	return maxT;
}

void Back_Tracking(int idx, int count) {

	if (count == M) {
		int smallTime = BFS();
		result.push_back(smallTime);
		return;
	}

	vector<vector<int>> copyArr = arr;

	for (int i = idx ; i < point.size(); i++) {

		if (idxVisited[i])continue;
		idxVisited[i] = true;
		selectedPoint.push_back({ point[i].first,point[i].second });
		Back_Tracking(i+1,count+1);
		arr = copyArr;
		selectedPoint.pop_back();
		idxVisited[i] = false;
	}
}

void Game_Start() {
    idxVisited.assign(point.size(), false);
    Back_Tracking(0, 0);

    int ans = 987654321;
    for (int t : result) if (t >= 0) ans = min(ans, t);

    cout << (ans == 987654321 ? -1 : ans);
}

int main(void) {
	Input();
	Game_Start();
}