백준 4179 불!

작성일 | In |

Problem : 불!

유형 : BFS

문제 해석

  • 지훈이가 미로에서 탈출할 수 있는지를 확인하라

문제 재해석

  • 불과 지훈이는 벽을 통과하지 못한다.
  • 지훈이는 불을 통화하지 못한다.
  • 지훈이는 가장 자리에 도착하면 탈출한다.

해결 전략

  • 1초씩 움직이므로 BFS로 최단거리를 재어 지훈이가 탈출 할 수 있는지 확인하면 된다.

구현, 설계

  • 불을 먼저 BFS 진행 시키며 불이 해당 위치에 도착한 시간을 기록한다.
  • 지훈이를 BFS 진행 시키되 가려는 곳에 불이 먼저 도착했으면 가지 못한다.
  • 지훈이가 가장자리에 도착하면 가장자리 도착시간 + 1 하여 탈출한다.

주의할점

  • visit 배열을 따로 두지 않고 -1로 초기화 했을 경우 조심 해야 한다.
  • 불이 -1초에 지나간 곳은 불이 지나간 것이 아니다.
1
2
3
4
5
4 4
###F
#J##
#..#
#..#

이런 반례가 있을 수 있다.

  • 가장자리 변은 2개가 아니라 총 4개가 있다.

코드

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
100
101
102
103
104
105
106
#include <bits/stdc++.h>
#define pp pair<int,int>
#define x first
#define y second

using namespace std;

int n, m;
char board[1002][1002];
int jh_time[1002][1002], fire_time[1002][1002];

const int dx[] = { -1,1,0,0 };
const int dy[] = { 0,0,-1,1 };
const char wall = '#';

queue<pp> jh_q, fire_q;

int Jh_Bfs() {

    while (!jh_q.empty()) {
        pp cur_jh = jh_q.front(); jh_q.pop();
        int cur_time = jh_time[cur_jh.x][cur_jh.y];

        if (cur_jh.x == 0 or cur_jh.y == 0 or cur_jh.x == n - 1 or cur_jh.y == m - 1) {
            return cur_time + 1;
        }

        for (int dir = 0; dir < 4; ++dir) {
            int nx = cur_jh.x + dx[dir];
            int ny = cur_jh.y + dy[dir];

            if (nx < 0 or nx >= n or ny < 0 or ny >= m) continue;
            if (board[nx][ny] == wall) continue;
            if (jh_time[nx][ny] != -1) continue;
            if (fire_time[nx][ny] != -1 and fire_time[nx][ny] <= cur_time + 1) continue;

            jh_time[nx][ny] = cur_time + 1;
            jh_q.push({ nx,ny });
        }
    }

    return -1;
}

void Fire_Bfs() {

    while (!fire_q.empty()) {
        pp cur_f = fire_q.front(); fire_q.pop();
        int cur_time = fire_time[cur_f.x][cur_f.y];
        
        for (int dir = 0; dir < 4; ++dir) {
            int nx = cur_f.x + dx[dir];
            int ny = cur_f.y + dy[dir];

            if (nx < 0 or nx >= n or ny < 0 or ny >= m) continue;
            if (board[nx][ny] == wall) continue;
            if (fire_time[nx][ny] != -1) continue;

            fire_time[nx][ny] = cur_time + 1;
            fire_q.push({ nx,ny });
        }
    }
}

void Solve() {
    Fire_Bfs();
    int result = Jh_Bfs();
    if (result == -1) cout << "IMPOSSIBLE\n";
    else cout << result << "\n";
}

void Input() {

    memset(jh_time, -1, sizeof(jh_time));
    memset(fire_time, -1, sizeof(fire_time));

    cin >> n >> m;

    string line;
    for (int i = 0; i < n; ++i) {
        cin >> line;
        for (int ii = 0; ii < m; ++ii) {
            board[i][ii] = line[ii];
            if (board[i][ii] == 'J') {
                jh_time[i][ii] = 0;
                jh_q.push({ i,ii });
            }
            else if (board[i][ii] == 'F') {
                fire_time[i][ii] = 0;
                fire_q.push({ i,ii });
            }
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);  cout.tie(NULL);
    freopen("input.txt", "r", stdin);

    Input();
    Solve();

    return 0;
}

피드백

  • BFS에서 visit배열을 따로 두지 않고 -1로 초기화 사용시에는 주의하자.
  • 문제 해답 조건에서 놓친 부분이 있지 않을까 고민하자. (가장자리 0 부분을 놓쳤었다)
  • 한번에 맞출 수 있도록 항상 주의하자.