[C++] 백준 9376번: 탈옥

🔗 문제

9376번: 탈옥

9376번: 탈옥

 

🖍 풀이

백준 9376번 탈옥 이 글을 보고 문제를 풀었습니다. 

백준 9376번 탈옥

 

 

생각해내야 하는 점

1. 죄수 1이 죄수 2를 데리고 바깥으로 나가는 경우
2. 죄수 2가 죄수 1을 데리고 바깥으로 나가는 경우
3. 상근이가 죄수 1, 2를 찾으러 바깥에서 안으로 잠입하는 경우

죄수가 1명이라면 BFS로 쉽게 풀었을 문제이지만, 죄수가 2명에다가 바깥 조력자가 있다는 점 때문에 문제가 어려웠다.

3명이 동시에 이동을 하다가 어느 점에서 만났을 때 탈옥하게 되므로, BFS를 3번 돌려 얻어낸 연 문의 수를 합산한 것 중 가장 작은 수를 구하면 된다. 

 

주의할 점은 3명이서 만나는 곳이 만약 문이라면 3명 동시에 문을 열어버린게 되니까 합산에서 -2 해줘야 한다.

이해가 안 갈까봐 첨언

• 죄수가 같이 있고 그걸 상근이 발견햇다면 셋이서 상근이가 온길로 쭉 가면 탈출할 수 있음

 

 

상근이가 밖에서 문을 열어주는 경우 고려하기

나는 문제를 읽고 상근이가 안에 들어오는걸 생각해내지 못해서 틀렸다.ㅋㅋ

맵을 입력 받을 때 사방을 상근이가 돌아다닐 수 있는 빈칸으로 채워준다.

char c;

for(int i=0; i<=N+1; ++i)
{
    for(int j=0; j<=M+1; ++j)
    {
        if(i == 0 || j == 0 || i == N+1 || j == M+1) // 상근이를 위한 공간
            map[i][j] = EMPTY;
        else
        {
            std::cin >> c;

            if(c=='$') prisoner.push_back({i, j});
            else if(c=='#') map[i][j] = DOOR;
            else if(c=='.') map[i][j] = EMPTY;
            else if(c=='*') map[i][j] = BLOCK;
        }
    }
}

 

또 상근이의 위치를 입력한다.

상근이의 위치에서부터 탈출구의 길이가 아니라 필요한 문의 개수만 세면 되니

상근이의 위치는 감옥 바깥이라면 어디든 상관이 없다 ~

prisoner.push_back({ 0, 0 }); // 상근이

 

---

소스 이해가 안될까봐 굳이 괜히 쓰는 글

맵의 상태가 4가지나 되는데 관리하기 헷갈려서 enum으로 파악해주었다.

빈 공간은 '.', 지나갈 수 없는 벽은 '*', 문은 '#', 죄수의 위치는 '$'이다.

enum STATE
{
    EMPTY,
    BLOCK,
    PRISONER,
    DOOR
};

STATE map[MAX][MAX];

 

거리가 가장 가까운 순으로 이동하기 위해서 priority_queue를 이용한다.

typedef std::pair<int, int> pii;
typedef std::pair<int, pii> pq_type;

std::priority_queue < pq_type, std::vector<pq_type>, std::greater<pq_type>> pq;

 

💾  소스

#include <iostream>
#include <vector>
#include <queue>
#include <functional>

typedef std::pair<int, int> pii;
typedef std::pair<int, pii> pq_type;

std::vector<pii> prisoner;

const int INF = 1e9;
const int MAX = 100 + 2;

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

enum STATE
{
    EMPTY,
    BLOCK,
    PRISONER,
    DOOR
};

int N, M;
STATE map[MAX][MAX];
int distance[3][MAX][MAX];

bool isValid(const int x, const int y)
{
    if(x<0 || y<0 || x>N+1 || y>M+1)
        return false;
    return true;
}

void BFS(const int num)
{
    bool visited[MAX][MAX] = {false, };
    std::priority_queue<pq_type, std::vector<pq_type>, std::greater<pq_type>> pq;

    pq.push({0, prisoner[num]});
    visited[prisoner[num].first][prisoner[num].second] = true;

    distance[num][prisoner[num].first][prisoner[num].second] = 0;

    while(!pq.empty())
    {
        int nowX = pq.top().second.first;
        int nowY = pq.top().second.second;
        pq.pop();

        for(int d=0; d<4; ++d)
        {
            int x = nowX + dx[d];
            int y = nowY + dy[d];

            if(!isValid(x, y) || map[x][y] == BLOCK || visited[x][y])
                continue;
            
            int cost = distance[num][nowX][nowY];
            if(map[x][y] == DOOR) ++cost;
            
            if(distance[num][x][y] > cost)
            {
                distance[num][x][y] = cost;
                visited[x][y] = true;
                pq.push({cost, {x, y}});
            }

        }
    }

}

void ready()
{
    std::cin >> N >> M;

    prisoner.clear();
    prisoner.push_back({0, 0}); // 상근이의 출발지

    for(int k=0; k<3; ++k)
    {
        for(int i=0; i<=N+1; ++i)
        {
            for(int j=0; j<=M+1; ++j)
            {
                distance[k][i][j] = INF;
            }
        }
    }

    char c;
    for(int i=0; i<=N+1; ++i)
    {
        for(int j=0; j<=M+1; ++j)
        {
            if(i == 0 || j == 0 || i == N+1 || j == M+1)
                map[i][j] = EMPTY;
            else
            {
                std::cin >> c;

                if(c=='$') prisoner.push_back({i, j});
                else if(c=='#') map[i][j] = DOOR;
                else if(c=='.') map[i][j] = EMPTY;
                else if(c=='*') map[i][j] = BLOCK;
            }
        }
    }

}

long long getAnswer()
{
    long long answer = INF;

    for(int j=0; j<=M; ++j)
    {
        for(int i=0; i<=N; ++i)
        {
            long long total = 0;
            for(int k=0; k<3; ++k)
            {
                total += distance[k][i][j];
            }
            total -= 2*(map[i][j] == DOOR);
            answer = (answer < total ? answer : total);
        }
    }

    return answer;
}

int main()
{
    int T; std::cin >> T;

    while(T--)
    {
        ready();

        for(int i=0; i<3; ++i)
            BFS(i);

        std::cout << getAnswer() << '\\n';
    }

    return 0;
}