백준 9376번 탈옥

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

9376번: 탈옥

 

 

 

 

 

<접근방법>

탐색 문제입니다.

 

일반적인 탐색문제와 다릅니다.

가중치가 이동한 거리와 상관없이 문을 연 횟수로 결정됩니다.

또 움직이는 말이 2개 입니다.

즉, 움직이는 말이 같은 문을 열고 갈 수도 있고 이 경우를 고려해야 합니다.

 

이것을 어떻게 고려할까요?

공통의 문은 한 번만 열어야 하는 것은 분명합니다.

그럼 죄수 둘 중 한 명이 아닌 제 3자를 도입해보는 건 어떨까요?

이 제 3자가 공통의 문은 열어주는 겁니다.

이 친구의 이름을 상근이라고 합시다.

 

그럼 상근이의 위치는 어디가 좋을까요?

죄수 둘은 한 번 겹치는 순간 그 경우가 최소의 경우가 될 수 밖에 없습니다.

처음에는 죄수 둘이 떨어져 있으니까 공통의 문을 확인할 수 있는 상근이의 위치는

감옥의 바깥이 되겠네요.

 

감옥의 가장자리를 밀어내고 (0, 0) 으로 세팅합시다.

 

그리고 이 세명이 bfs로 탐색을 합니다.

여기서 주의할 점이 있습니다.

이 문제에서의 탐색은 가중치가 거리가 아닌 문을 연 횟수입니다.

즉, 큐에 넣었을 시에 문을 연 횟수가 작은 순서대로 나오게 만들어야 합니다.

 

그리고 각 말들에 대한 가중치를 저장한 2차원 배열들을 모두 더한 후

값이 가장 작은 것이 답이 됩니다.

이때, 3명 중 한 명만 문을 열면 되므로 3명이 문에서 만났을 경우를 고려해야 합니다.

 

 

<느낀 점>

첫 플레 문제인데 내가 풀기엔 버겁다고 느꼈다.

탐색에 대한 틀에 박힌 생각을 깨준 문제다.

 

제 3자의 도입을 어떻게 생각할 수 있을까

대부분이 제 3자의 도입으로 문제를 풀었다. 풀이가 이렇게 귀결될 수 밖에 없는 이유가 뭘까

 

---

 

 

 

<코드>

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


struct point {
	int y, x, val;
};

const int INF = 7654321;
int tc, n, m, map[104][104];
int dy[4] = { 1, -1, 0, 0 };
int dx[4] = { 0, 0, 1, -1 };
int p[3][104][104];

struct cmp{
	bool operator()(point a, point b) {
		return a.val > b.val;
	}
};

int res = INF;

vector<point> man;

void bfs(int y, int x, int num) {
	priority_queue<point, vector<point>, cmp> q;
	bool visit[104][104] = { false, };

	q.push({y, x, 0});
	visit[y][x] = true;
	p[num][y][x] = 0;

	while (!q.empty()) {
		point t = q.top();
		q.pop();

		for (int i = 0; i < 4; i++) {
			int ty = t.y + dy[i];
			int tx = t.x + dx[i];
			int tval = t.val;

			if (ty < 0 || ty >= n + 2 || tx < 0 || tx >= m + 2) continue;
			if (visit[ty][tx] || map[ty][tx] == 1) continue;

			if (map[ty][tx] == 2) tval++;

			q.push({ty, tx, tval});
			visit[ty][tx] = true;
			p[num][ty][tx] = tval;
		}
	}
}

int main() {
	cin >> tc;
	while (tc--) {
		man.clear();

		man.push_back({ 0, 0 });

		cin >> n >> m;
		for (int i = 0; i < n + 2; i++) {
			for (int j = 0; j < m + 2; j++) {
				if (i == 0 || i == n + 1 || j == 0 || j == m + 1) {
					map[i][j] = 0;
					continue;
				}

				char c;
				cin >> c;

				if (c == '.') {
					map[i][j] = 0;
				}
				else if (c == '#') {
					map[i][j] = 2;
				}
				else if (c == '*') {
					map[i][j] = 1;
				}
				else {
					map[i][j] = 3;
					man.push_back({ i, j });
				}
			}
		}

		for (int z = 0; z < 3; z++) {
			for (int i = 0; i < n; i++) {
				for (int j = 0; j < m; j++) {
					//p[z][i][j] = INF;
				}
			}
		}

		for (int num = 0; num < 3; num++) {
			bfs(man[num].y, man[num].x, num);
		}


		long long ans = INF;
		for (int i = 1; i < n + 1; i++) {
			for (int j = 1; j < m + 1; j++) {
				if (map[i][j] == 1) continue;

				long long tmp = 0;
				for (int z = 0; z < 3; z++) {
					tmp += p[z][i][j];
				}

				if (map[i][j] == 2) tmp -= 2;

				ans = min(ans, tmp);

			}
		}

		cout << ans << '\n';
	}

	return 0;
}