[C/C++] 백준 #3055 탈출(너비 우선 탐색)

백준 온라인 저지 문제 #3055는 “탈출”이라는 제목의 문제로, 주어진 2차원 맵에서 고슴도치가 물을 피하면서 동굴로 탈출하는 경로를 찾는 시뮬레이션 문제입니다. 문제의 주요 포인트는 다음과 같습니다.

문제 설명

1. 맵 구성: 고슴도치는 S로, 동굴은 D로 표시되어 있습니다. 물은 *로 표시되며 매 시간마다 상하좌우로 확산합니다. 빈 공간은 .로 표현됩니다.
2. 목표: 고슴도치는 물이 찰 예정인 칸을 피하면서 최소한의 이동 시간으로 동굴(D)에 도달해야 합니다.
3. 제약 조건:
• 고슴도치는 한 번에 상하좌우로 한 칸씩 움직일 수 있습니다.
• 물은 매 시간마다 고슴도치보다 먼저 확산되어 고슴도치의 경로를 막을 수 있습니다.
4. 출력 조건: 고슴도치가 동굴로 탈출할 수 있는 최소 시간을 출력하며, 탈출이 불가능한 경우 KAKTUS를 출력합니다.

풀이 접근법

이 문제는 BFS(너비 우선 탐색)를 활용해 해결할 수 있습니다. 물의 확산과 고슴도치의 이동을 각각 따로 큐에 저장하고, 물이 먼저 확산된 후 고슴도치가 이동하는 방식으로 시뮬레이션을 진행합니다.

 

escape path

 

제가 작성한 소스 전체입니다.

//--------------------------------------
//    baekjoon #3055 - exodus
//        - by Aubrey Choi
//        - created at 2019-10-11
//--------------------------------------
#include <stdio.h>
#include <queue>

int main()
{
    int r, c, s, e, y, x, p;
    char map[50][52]; static int v[2500];
    std::queue<int> q;
    scanf("%d%d",&r,&c);
    for(int i=0;i<r;i++) scanf("%s", map[i]);
    for(int i=0;i<r;i++) for(int j=0;j<c;j++)
    {
        int t=i*50+j;
        if(map[i][j]=='*') { q.push(0x10000|t); map[i][j]='X'; }
        else if(map[i][j]=='S') s=t;
        else if(map[i][j]=='D') e=t;
    }
    q.push(s); v[s]=1;
    while(!q.empty())
    {
        s=q.front(); q.pop();
        y=(s&0xffff)/50, x=(s&0xffff)%50, p=v[s&0xffff];
        if(s==e) break;
        const int d[4][2] = { 0,1, 1,0, 0,-1, -1,0 };
        for(int i=0;i<4;i++)
        {
            int ny=y+d[i][0], nx=x+d[i][1], t=ny*50+nx;
            if(ny<0||ny>=r||nx<0||nx>=c||map[ny][nx]=='X') continue;
            if(s>>16) { if(t!=e) { map[ny][nx]='X'; q.push(0x10000|t); } continue; }
            if(v[t]) continue;
            q.push(t);
            v[t]=p+1;
        }
    }
    if(s==e) printf("%d\n", p-1); else puts("KAKTUS");
}

 

 

물이 확산되고 고슴도치가 이동하는 과정을 시뮬레이션하여 동굴에 도달하는 최소 시간을 찾는 프로그램입니다. 코드의 주요 부분을 설명드리겠습니다.

주요 변수 설명

• r, c: 맵의 행과 열의 크기입니다.
• s: 고슴도치의 초기 위치를 나타내는 좌표 값입니다.
• e: 동굴 위치를 나타내는 좌표 값입니다.
• map[50][52]: 맵 정보를 저장하는 2차원 배열입니다. 각 칸의 상태는 고슴도치, 물, 동굴, 빈 칸, 또는 막힌 칸으로 구분됩니다.
• v[2500]: 각 위치까지의 방문 여부와 도달 시간을 기록하는 배열입니다. 2500은 최대 맵 크기(50*50)를 의미합니다.
• q: BFS(너비 우선 탐색)에서 사용할 큐로, 현재 물의 확산과 고슴도치의 이동을 처리합니다.

코드 설명

1. 맵 입력 및 초기 설정:

scanf("%d%d", &r, &c);
for(int i = 0; i < r; i++) scanf("%s", map[i]);

• r과 c를 입력 받아 맵의 행과 열 크기를 설정하고, 맵 데이터를 입력받습니다.

2. 초기 위치 설정:

for(int i = 0; i < r; i++)
    for(int j = 0; j < c; j++) {
        int t = i * 50 + j;
        if(map[i][j] == '*') { q.push(0x10000 | t); map[i][j] = 'X'; }
        else if(map[i][j] == 'S') s = t;
        else if(map[i][j] == 'D') e = t;
    }

• '*'는 물의 위치입니다. 물 위치를 큐에 넣고, 해당 위치는 확산이 끝났음을 의미하는 'X'로 변경합니다.
• 'S'는 고슴도치의 시작 위치이고, 'D'는 동굴 위치입니다.
• t는 (i, j) 좌표를 1차원 배열 인덱스로 변환한 값입니다.

3. BFS 탐색 시작:

q.push(s); v[s] = 1;
while(!q.empty()) {
    s = q.front(); q.pop();
    y = (s & 0xffff) / 50, x = (s & 0xffff) % 50, p = v[s & 0xffff];
    if(s == e) break;

• 고슴도치의 시작 위치를 큐에 넣고, v 배열을 통해 방문 처리합니다.
• BFS를 이용하여 큐에서 현재 위치를 꺼내 처리합니다.

4. 이동 처리:

for(int i = 0; i < 4; i++) {
    int ny = y + d[i][0], nx = x + d[i][1], t = ny * 50 + nx;
    if(ny < 0 || ny >= r || nx < 0 || nx >= c || map[ny][nx] == 'X') continue;
    if(s >> 16) { if(t != e) { map[ny][nx] = 'X'; q.push(0x10000 | t); } continue; }
    if(v[t]) continue;
    q.push(t);
    v[t] = p + 1;
}

• d 배열을 통해 상하좌우로 이동할 수 있습니다.
• 물이 확산할 경우, s >> 16이 참이 되어 0x10000 비트를 확인해 물 확산 여부를 구분합니다. 물은 동굴에 확산할 수 없도록 예외처리합니다.
• 고슴도치가 이동하는 경우, 이미 방문한 곳은 건너뜁니다.

5. 결과 출력:

if(s == e) printf("%d\n", p - 1); else puts("KAKTUS");

• BFS 탐색에서 고슴도치가 동굴에 도달하면 그때의 시간 p-1을 출력합니다.
• 고슴도치가 동굴에 도달하지 못할 경우 KAKTUS를 출력합니다.

이 코드는 물의 확산과 고슴도치의 이동을 BFS로 시뮬레이션하여 최단 경로를 찾는 문제입니다.