9376 탈옥

1. 문제

2. 코드

#include "pch.h"
#include <stdio.h>
#include <queue>
#include <iostream>
#include <cstring>
#define _CRT_SECURE_NO_WARNINGS
 
using namespace std;
 
char map[102][102];
int m1[102][102];
int m2[102][102];
int m3[102][102];
int n, m;
int row[4] = { -1,1,0,0 };
int col[4] = { 0,0,1,-1 };
 
struct node{
    int x, y;
};
 
void solve(node src, int map[102][102]);
 
int main()
{
    int T;
    scanf("%d", &T);
    while (T--) {
        node pos1 = { -1,-1 }, pos2;
        scanf("%d %d", &n, &m);
 
        for (int h = 0; h <= n + 1; h++) {
            for (int w = 0; w <= m + 1; w++)
                map[h][w] = '.';
        }
 
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                cin >> map[i][j];
                if (map[i][j] == '$') {
                    if (pos1.x == -1) {
                        pos1.x = i;
                        pos1.y = j;
                    }
                    else {
                        pos2.x = i;
                        pos2.y = j;
                    }
                }
            }
        }
        //m1,m2,m3를 -1로 채운다.
        memset(m1, -1, sizeof(m1));
        memset(m2, -1, sizeof(m2));
        memset(m3, -1, sizeof(m3));
 
        solve({ 0,0 }, m1);
        solve(pos1, m2);
        solve(pos2, m3);
 
        
        
        int ans = 10000;
        for (int i = 1; i <= n; i++) {
            for (int j = 0; j <= m; j++) {
                if (map[i][j] == '#') {
                    ans = min(ans, m1[i][j] + m2[i][j] + m3[i][j] - 2);
                }
            }
        }
        //죄수들의 위치가 최소값이면 그게 답
        ans = min(ans, m1[pos1.x][pos1.y] + m2[pos1.x][pos1.y] + m3[pos1.x][pos1.y]);
        ans = min(ans, m1[pos2.x][pos2.y] + m2[pos2.x][pos2.y] + m3[pos2.x][pos2.y]);
 
        printf("%d\n", ans);
    }
    
}
 
//배열의 값이 자동으로 바뀐다. 
void solve(node src, int board[102][102])
{
    queue<node> q;
    q.push(src);
    board[src.x][src.y] = 0;
    while (!q.empty()) {
        node cur = q.front();
        q.pop();
        for (int i = 0; i < 4; i++) {
            int nx = cur.x + row[i];
            int ny = cur.y + col[i];
            if (nx <0 || ny<0 || nx > n + 1 || ny > m + 1)
                continue;
            if (map[nx][ny] == '#') {
                if (board[cur.x][cur.y] + 1 < board[nx][ny] || board[nx][ny] == -1) {
                    board[nx][ny] = board[cur.x][cur.y] + 1;
                    q.push({ nx,ny });
                }
            }
            else if (map[nx][ny] != '*') {
                if (board[cur.x][cur.y] < board[nx][ny] || board[nx][ny] == -1) {
                    board[nx][ny] = board[cur.x][cur.y];
                    q.push({ nx,ny });
                }
            }
        }
    }
    
}

3. 후기

엄청 어려운 문제였다. 탈출하는 방법은 세 가지 이다.

 1) 죄수 1이 죄수2를 데리고 바깥으로 나가는 경우

 2) 죄수2가 죄수1을 데리고 바깥으로 나가는 경우

 3) 외부의 조력자가 죄수1, 2를 찾으러 잠입하는 경우

bfs를 이용해 문을 몇개를 열어야 도달할 수 있는지를 나타내는 맵을 그릴 수 있다. 맵 3개를 더해서 최소의 값을 뽑아내는데, 문의 경우는 -2를 해준다. 세 명이 모두 문을 열어야 할 필요가 없기 때문이다. 

출처 - https://stack07142.tistory.com/145