BOJ 9379 탈옥 / C++

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

9376번: 탈옥

백준 온라인저지 9379번 탈옥문제입니다.

 

아이디어

골드 등급 문제만 풀다가 플레티넘 등급 문제로 넘어갈까해서 풀어본 문제인데 플레의 벽은 높았다...

방법을 찾기위해 이틀정도 고민을 했었고, 그 방법으로는 이전에 풀었던 카카오 기출이 생각나서 비슷한 느낌의 풀이를 고민을 했습니다.

두 죄수가최소한의 문을 통과하여 한 지점에 모이고 그 지점에서 최소한의 문을 통과하여 외부로 나가는 길을 찾아야 한다는 생각을 했습니다. 알고리즘은 BFS를 이용한 완전탐색을 해야하지 않을까 했는데 아무리 생각해도 각이 안나와서 풀이를 참고하였습니다.

아래의 코드는 상근이, 죄수1, 죄수2가 한 지점에 모이면 탈출이 가능하다는 점을 이용한 풀이이고, 알고리즘은 다익스트라처럼 그래프의 노드까지 가기위해 열어야하는 문의 최솟값이 담긴 가중치map을 BFS를 이용하여 만들어야합니다. 상근이, 죄수1, 죄수2의 가중치map을 모두 만든 후 셋의 가중치 map을 비교하여 셋이 모두 모일 수 있는 지점을 하나씩 탐색하여 최소의 문을 통과할 수 있는 지점을 찾아내야 합니다.

디테일하게 봐야하는 부분은 상근이가 감옥으로 접근할 테두리를 만들어주는 부분과 가중치 map을 만들때 queue가 아닌 deqeue를 사용한다는 점입니다.

아래의 주석을 보고 궁금하신점이나 잘못된 부분은 댓글을 통해 의견 전달 부탁드립니다.

 

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

class Point {
public:
	int x, y;
	Point(int a, int b) {
		y = a;
		x = b;
	}
	Point() {}
};

int t,h,w;
vector<vector<char>> map;
vector<Point> prisoner;

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


void input() {
	cin >> h >> w;
	//상근이가 접근할 테두리 만들어야 하기 때문에 +2
	map = vector<vector<char>>(h+2, vector<char>(w+2, '.'));
	prisoner.clear();
	for (int i = 1; i <= h ; i++) {
		for (int j = 1; j <=w; j++) {
			cin >> map[i][j];
			if (map[i][j] == '$') {
				prisoner.push_back(Point(i, j));
			}
		}
	}
}

// char map을 각 공간에 도착하기 위해 열어야 하는 문의 개수로 표현된 int map을 만들어야 함
// 특정 지점부터 BFS를 이용하여 벽일경우만 빼고 모두 탐색하여 문의 개수를 기록
// p는 상근, 죄수1, 2의 위치를 의미하며 BFS가 시작되는 지점임
vector<vector<int>> convertChar2Int(Point p) {
	int n = map.size();
	int m = map[0].size();
	vector<vector<int>> result(n, vector<int>(m, -1));
	result[p.y][p.x] = 0; // BFS의 시작점은 문일 수 없기 때문에 0시작
	deque<Point> dq; // 노드간 가중치가 0또는 +1이기 때문에 최소한으로 문을 통과한 노드를 먼저 탐색하기 위해 deque사용
	dq.push_front(p);
	while (!dq.empty()) {
		Point cur = dq.front();
		dq.pop_front();
		for (int i = 0; i < 4; i++) {
			Point next(cur.y + dy[i], cur.x + dx[i]);
			if (next.y < 0 || next.y >= n || next.x < 0 || next.x >= m)continue;
			if (map[next.y][next.x] == '*') continue;
			if (result[next.y][next.x] > -1) continue;
			if (map[next.y][next.x] == '#') {
				result[next.y][next.x] = result[cur.y][cur.x] + 1;
				dq.push_back(next); //문을 통과한 지점은 +1 가중치를 가지는데 문을 통과한 최솟값을 구해야 하기 때문에 뒤쪽으로 넣어줌
			}
			else {
				result[next.y][next.x] = result[cur.y][cur.x];
				dq.push_front(next);//문을 통과하지 않은 지점은 가중치를 가지지 않기 때문에 앞으로 넣어줌
			}

		}
	}
	return result;
}

void solution() {
	vector<vector<int>> intMap1 = convertChar2Int(Point(0, 0));     //상근이의 int map
	vector<vector<int>> intMap2 = convertChar2Int(prisoner.front());//죄수1의 int map
	vector<vector<int>> intMap3 = convertChar2Int(prisoner.back());//죄수2의 int map

	//상근 죄수1, 죄수 2가 만날 수 있는 공간까지 열어야 하는 문의 개수를 구함
	int sol = 987654321;
	for (int i = 1; i <= h; i++) {
		for (int j = 1; j <= w; j++) {
			if (map[i][j] == '*') continue;
			if (intMap1[i][j] == -1 || intMap2[i][j] == -1 || intMap3[i][j] == -1) continue; //60%에서 막힘 아래반례
			int temp = intMap1[i][j] + intMap2[i][j] + intMap3[i][j]; // 세명이 모두 만나는 지점까지 열린 문의 개수
			if (map[i][j] == '#') temp -= 2; // 문에서 만날 경우 상근, 죄수1, 죄수2 모두가 문을 열기 때문에 2명의 카운트를 빼야함
			if (sol > temp) sol = temp;
		}
	}
	cout << sol << "\n";
}

int main(void) {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	cin >> t;
	while (t--) {
		input();
		solution();
	}
}
//https://www.acmicpc.net/problem/9376
/*
1
3 5
*****
#$∗$#
*****

정답 : 2
*/