[BOJ] 9376 - 탈옥
https://www.acmicpc.net/problem/9376
문제
상근이는 감옥에서 죄수 두 명을 탈옥시켜야 한다. 이 감옥은 1층짜리 건물이고, 상근이는 방금 평면도를 얻었다.
평면도에는 모든 벽과 문이 나타나있고, 탈옥시켜야 하는 죄수의 위치도 나타나 있다. 감옥은 무인 감옥으로 죄수 두 명이 감옥에 있는 유일한 사람이다.
문은 중앙 제어실에서만 열 수 있다. 상근이는 특별한 기술을 이용해 제어실을 통하지 않고 문을 열려고 한다. 하지만, 문을 열려면 시간이 매우 많이 걸린다. 두 죄수를 탈옥시키기 위해서 열어야 하는 문의 개수를 구하는 프로그램을 작성하시오. 문을 한 번 열면 계속 열린 상태로 있는다.
입력
첫째 줄에 테스트 케이스의 개수가 주어진다. 테스트 케이스의 수는 100개를 넘지 않는다.
첫째 줄에는 평면도의 높이 h와 너비 w가 주어진다. (2 ≤ h, w ≤ 100) 다음 h개 줄에는 감옥의 평면도 정보가 주어지며, 빈 공간은 '.', 지나갈 수 없는 벽은 '*', 문은 '#', 죄수의 위치는 '$'이다.
상근이는 감옥 밖을 자유롭게 이동할 수 있고, 평면도에 표시된 죄수의 수는 항상 두 명이다. 각 죄수와 감옥의 바깥을 연결하는 경로가 항상 존재하는 경우만 입력으로 주어진다.
출력
각 테스트 케이스마다 두 죄수를 탈옥시키기 위해서 열어야 하는 문의 최솟값을 출력한다.
예제 입출력
- 예제 입력 1
3
5 9
****#****
*..#.#..*
****.****
*$#.#.#$*
*********
5 11
*#*********
*$*...*...*
*$*.*.*.*.*
*...*...*.*
*********.*
9 9
*#**#**#*
*#**#**#*
*#**#**#*
*#**.**#*
*#*#.#*#*
*$##*##$*
*#*****#*
*.#.#.#.*
*********
- 예제 출력 1
4
0
9
Solution
#include <iostream>
#include <vector>
#include <queue>
#define MAX 102
#define INF 987654
using namespace std;
int N, M;
char MATRIX[MAX][MAX];
int Dist[3][MAX][MAX];
int dx[4] = {0, 0, 1, -1};
int dy[4] = {1, -1 ,0 ,0};
vector<pair<int, int>> prisoner;
void init(){
prisoner.clear();
for(int i = 0; i < MAX; i++){
fill_n(MATRIX[i], MAX, '.');
}
for(int i = 0; i < 3; i++){
for(int j = 0; j < MAX; j++){
fill_n(Dist[i][j], MAX, INF);
}
}
}
void Dijkstra(int X, int Y, int Pos){
priority_queue<pair<int, pair<int, int>>> PQ;
PQ.push({0, {X, Y}});
Dist[Pos][X][Y] = 0;
while (!PQ.empty()){
int x = PQ.top().second.first;
int y = PQ.top().second.second;
int cost = -PQ.top().first;
PQ.pop();
if(Dist[Pos][x][y] < cost) continue;
for(int i = 0; i < 4; i++){
int nx = x + dx[i];
int ny = y + dy[i];
int curCost = cost;
if(nx >= 0 && nx <= N+1 && ny >= 0 && ny <= M+1 && MATRIX[nx][ny] != '*'){
if(MATRIX[nx][ny] == '#') curCost++;
if(Dist[Pos][nx][ny] > curCost){
PQ.push({-curCost, {nx, ny}});
Dist[Pos][nx][ny] = curCost;
}
}
}
}
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
int T; cin >> T;
while(T--){
init();
cin >> N >> M;
for(int i = 1; i <= N; i++){
for(int j = 1; j <= M; j++) {
cin >> MATRIX[i][j];
if(MATRIX[i][j] == '$') prisoner.push_back({i, j});
}
}
Dijkstra(0, 0, 0);
Dijkstra(prisoner[0].first, prisoner[0].second, 1);
Dijkstra(prisoner[1].first, prisoner[1].second, 2);
int minimum = 99999;
int cost = 99999;
for(int i = 0; i <= N+1; ++i){
for(int j = 0; j <= N+1; ++j){
if(MATRIX[i][j] != '*'){
cost = Dist[0][i][j] + Dist[1][i][j] + Dist[2][i][j];
if(MATRIX[i][j] == '#') cost -= 2;
minimum = min(minimum, cost);
}
}
}
cout << minimum << '\n';
}
}
3
5 9
****#****
*..#.#..*
****.****
*$#.#.#$*
*********
5 11
*#*********
*$*...*...*
*$*.*.*.*.*
*...*...*.*
*********.*
9 9
*#**#**#*
*#**#**#*
*#**#**#*
*#**.**#*
*#*#.#*#*
*$##*##$*
*#*****#*
*.#.#.#.*
*********
4
0
9
#include <iostream>
#include <vector>
#include <queue>
#define MAX 102
#define INF 987654
using namespace std;
int N, M;
char MATRIX[MAX][MAX];
int Dist[3][MAX][MAX];
int dx[4] = {0, 0, 1, -1};
int dy[4] = {1, -1 ,0 ,0};
vector<pair<int, int>> prisoner;
void init(){
prisoner.clear();
for(int i = 0; i < MAX; i++){
fill_n(MATRIX[i], MAX, '.');
}
for(int i = 0; i < 3; i++){
for(int j = 0; j < MAX; j++){
fill_n(Dist[i][j], MAX, INF);
}
}
}
void Dijkstra(int X, int Y, int Pos){
priority_queue<pair<int, pair<int, int>>> PQ;
PQ.push({0, {X, Y}});
Dist[Pos][X][Y] = 0;
while (!PQ.empty()){
int x = PQ.top().second.first;
int y = PQ.top().second.second;
int cost = -PQ.top().first;
PQ.pop();
if(Dist[Pos][x][y] < cost) continue;
for(int i = 0; i < 4; i++){
int nx = x + dx[i];
int ny = y + dy[i];
int curCost = cost;
if(nx >= 0 && nx <= N+1 && ny >= 0 && ny <= M+1 && MATRIX[nx][ny] != '*'){
if(MATRIX[nx][ny] == '#') curCost++;
if(Dist[Pos][nx][ny] > curCost){
PQ.push({-curCost, {nx, ny}});
Dist[Pos][nx][ny] = curCost;
}
}
}
}
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
int T; cin >> T;
while(T--){
init();
cin >> N >> M;
for(int i = 1; i <= N; i++){
for(int j = 1; j <= M; j++) {
cin >> MATRIX[i][j];
if(MATRIX[i][j] == '$') prisoner.push_back({i, j});
}
}
Dijkstra(0, 0, 0);
Dijkstra(prisoner[0].first, prisoner[0].second, 1);
Dijkstra(prisoner[1].first, prisoner[1].second, 2);
int minimum = 99999;
int cost = 99999;
for(int i = 0; i <= N+1; ++i){
for(int j = 0; j <= N+1; ++j){
if(MATRIX[i][j] != '*'){
cost = Dist[0][i][j] + Dist[1][i][j] + Dist[2][i][j];
if(MATRIX[i][j] == '#') cost -= 2;
minimum = min(minimum, cost);
}
}
}
cout << minimum << '\n';
}
}
많이 어렵다. 다익스트라 알고리즘을 안다고 해결 할 수 있는 문제가 아니다.
우선 관점을 확고하게 둘 필요가 있다.
1. 감옥 안에 있는 죄수 2명
2. 그 둘을 탈출시키기 위해 존재하는 1명
이 세 명을 기준으로 다익스트라 알고리즘을 돌리면 된다.
주 된 아이디어는 다음과 같다. 현재 데이터를 입력 받을 때는 1부터 N ~ 1부터 M 사이의 데이터를 입력받았다. 하지만 전체 감옥 끝에 또 다른 공간이 있으면 어떨까?
감옥 테두리 외에 또 다른 공간이 존재하고 0, 0
위치에서 상근이가 문을 열어주는 입장이라면 어떨까 하는 아이디어가 중요하다.
void init(){
prisoner.clear();
for(int i = 0; i < MAX; i++){
fill_n(MATRIX[i], MAX, '.');
}
for(int i = 0; i < 3; i++){
for(int j = 0; j < MAX; j++){
fill_n(Dist[i][j], MAX, INF);
}
}
}
그러므로 애초에 초기 세팅에서 MATRIX
데이터 전체를 .
으로 처리한다. 귀찮게 일을 두번하지 않게 하기 위해서.
int N, M;
char MATRIX[MAX][MAX];
int Dist[3][MAX][MAX];
int dx[4] = {0, 0, 1, -1};
int dy[4] = {1, -1 ,0 ,0};
vector<pair<int, int>> prisoner;
void Dijkstra(int X, int Y, int Pos){
priority_queue<pair<int, pair<int, int>>> PQ;
PQ.push({0, {X, Y}});
Dist[Pos][X][Y] = 0;
while (!PQ.empty()){
int x = PQ.top().second.first;
int y = PQ.top().second.second;
int cost = -PQ.top().first;
PQ.pop();
if(Dist[Pos][x][y] < cost) continue;
for(int i = 0; i < 4; i++){
int nx = x + dx[i];
int ny = y + dy[i];
int curCost = cost;
if(nx >= 0 && nx <= N+1 && ny >= 0 && ny <= M+1 && MATRIX[nx][ny] != '*'){
if(MATRIX[nx][ny] == '#') curCost++;
if(Dist[Pos][nx][ny] > curCost){
PQ.push({-curCost, {nx, ny}});
Dist[Pos][nx][ny] = curCost;
}
}
}
}
}
2차원 배열 데이터 내에서 다익스트라를 쓰는것과 동일하다. 여기서 Cost는 문을 여는 비용. 가장 첫 번째 Cost는 문을 아직 열지 않았으니 0 부터 시작한다.
각 인물별로 Dist 데이터는 따로 처리한다. 현재 위치에서 비용을 처리할 때, 만약 문을 만나면 비용을 1 추가한다.
하지만 특정 위치에서 여러 방향에 문이 있는 상황도 존재한다. 이럴 때를 대비하여 for문 내에서 4 방향에 대한 처리를 할 때 cost 데이터는 독립 된 변수로 처리해야 한다. (필자는 이 부분에서 실수가 계속 일어났었다.)
0,0에서 상근이가 열어주는 경우, 나머지 각 죄수들이 알아서 여는 경우 총 3가지 경우에 대하여 Dist 배열을 각각 구한다. 그 후 이 세가지 배열 내에 데이터를 비교하면 된다.
int minimum = 99999;
int cost = 99999;
for(int i = 0; i <= N+1; ++i){
for(int j = 0; j <= N+1; ++j){
if(MATRIX[i][j] != '*'){
cost = Dist[0][i][j] + Dist[1][i][j] + Dist[2][i][j];
if(MATRIX[i][j] == '#') cost -= 2;
minimum = min(minimum, cost);
}
}
}
cout << minimum << '\n';
모든 가능한 좌표들을 서치하며 벽이 아닌 경우에는 Dist 데이터에 값이 갱신되어있을테니 세 가지 경우에 대한 Dist 값을 갱신한다. 만약 벽을 만나면 -2를 해 준다. 어차피 세 경우 다 해당 위치에서 Cost를 +1 했을테니 한 가지 경우로 처리하기 위해서다.
역시 플레티넘 문제는 어렵다. 매우 매우 고민하고 도움도 많이 받았던 문제. 기억에 각인하기 위해 기록한다.
Author And Source
이 문제에 관하여([BOJ] 9376 - 탈옥), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@sierra9707/BOJ-9376-탈옥저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)