[백준 / BOJ / GOLD 4] 3055 번 : 탈출

지나가던 개발자 2020. 4. 1. 22:50

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

3055번: 탈출

문제 사악한 암흑의 군주 이민혁은 드디어 마법 구슬을 손에 넣었고, 그 능력을 실험해보기 위해 근처의 티떱숲에 홍수를 일으키려고 한다. 이 숲에는 고슴도치가 한 마리 살고 있다. 고슴도치는 제일 친한 친구인 비버의 굴로 가능한 빨리 도망가 홍수를 피하려고 한다. 티떱숲의 지도는 R행 C열로 이루어져 있다. 비어있는 곳은 '.'로 표시되어 있고, 물이 차있는 지역은 '*', 돌은 'X'로 표시되어 있다. 비버의 굴은 'D'로, 고슴도치의 위치는 'S'로 나

www.acmicpc.net

문제 접근법

단순 이동만이 아니라 물이 매턴마다 차오르는것을 신경써야 하는 문제이다.
주어진 맵을 그리기 위한 2차원 배열 1개와 물이 차오르는 맵을 그릴 2차원 배열 1개를 준비한다.
물이 차오르는 맵을 BFS를 통해 몇턴에 물이 차는지를 기록한다.
고슴도치를 이동횟수와 물이 차오르는 맵의 기록을 비교하여 고슴도치를 이동시킨다.
단 물이 차오를 곳에는 고슴도치가 이동할 수 없음을 알아야 한다.

아래는 코드입니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99

#include<cstdio>
#include<queue>
 
using namespace std;
 
int waterMap[51][51];
char escapeMap[51][51];
bool visit[51][51];
bool check;
 
int dx[] = { 0, 0, 1, -1 };
int dy[] = { 1, -1, 0, 0};
 
int main()
{
    int r, c;
    queue<pair<pair<int, int>, int>> q;
    queue<pair<int, int>> q1;
 
    scanf("%d %d", &r, &c);
 
    for (int i = 1; i <= r; i++)
    {
        for (int j = 1; j <= c; j++)
        {
            scanf(" %c", &escapeMap[i][j]);
            waterMap[i][j] = 9999;
 
            if (escapeMap[i][j] == 'S')
            {
                q.push(make_pair(make_pair(i, j), 0));
            }
            else if (escapeMap[i][j] == '*')
            {
                q1.push(make_pair(i, j));
                waterMap[i][j] = 0;
            }
        }
    }
 
    while (!q1.empty())
    {
        int x = q1.front().first;
        int y = q1.front().second;
        q1.pop();
 
        for (int i = 0; i < 4; i++)
        {
            int nx = x + dx[i];
            int ny = y + dy[i];
 
            if (nx < 1 || nx > r || ny < 1 || ny > c || escapeMap[nx][ny] == 'D' || escapeMap[nx][ny] == 'X') continue;
 
            if (escapeMap[nx][ny] == '.' && waterMap[nx][ny] - 1 > waterMap[x][y])
            {
                waterMap[nx][ny] = waterMap[x][y] + 1;
                q1.push(make_pair(nx, ny));
            }
        }
    }
 
    while (!q.empty())
    {
        int x = q.front().first.first;
        int y = q.front().first.second;
        int moveCount = q.front().second;
        visit[x][y] = true;
 
        q.pop();
 
        if (escapeMap[x][y] == 'D')
        {
            printf("%d", moveCount);
            check = true;
            break;
        }
 
        for (int i = 0; i < 4; i++)
        {
            int nx = x + dx[i];
            int ny = y + dy[i];
 
            if (nx < 1 || nx > r || ny < 1 || ny > c || escapeMap[nx][ny] == 'X') continue;
 
            if ((escapeMap[nx][ny] == 'D' || escapeMap[nx][ny] == '.') && moveCount < waterMap[nx][ny] - 1 && !visit[nx][ny])
            {
                visit[nx][ny] = true;
                q.push(make_pair(make_pair(nx, ny), moveCount + 1));
            }
        }
    }
 
    if (!check)
    {
        printf("%s", "KAKTUS");
    }
 
    return 0;
}
Colored by Color Scripter

 