[BOJ 4179] 불!

썸네일

4179번: 불!

문제 설명

예제

 

아래 사진은 시간별 지훈이(왹깅)와 불(🔥)의 위치를 나타낸 그림이다.

이 때 주의할 것은 지훈이와 불이 '동시에' 움직인다는 것이다.

지훈이가 움직인 다음 불이 붙거나, 불이 붙은 다음 지훈이가 움직이는 것이 아니다.

 

t=2일 때 미로의 가장자리에 도착하였고, 한 칸을 더 움직여 t=3일 때 지훈이는 미로를 탈출할 수 있다.

 

구현 아이디어

처음에는 지훈이가 움직일 수 있는 경로가 여러 개라고 생각해서 DFS로 완전탐색을 해야 한다고 생각했다.

하지만 지훈이와 불을 동시에 움직이는 코드를 적는 것이 어려웠고, 결국 다른 사람의 풀이를 참고하여 문제를 풀 수 있었다. 🥲

 

문제를 풀기 위한 핵심 아이디어는 아래와 같다.

핵심 아이디어
1. 불의 최단거리와 지훈이의 최단거리를 비교하자. 지훈이의 최단거리가 불의 최단거리보다 작다면 지훈이는 불이 붙기 전 해당 위치를 갈 수 있는 것이다.
2. 최단거리이므로 DFS가 아닌 BFS를 사용해야 한다.
3. 불은 없을수도 있고, 2개 이상일 수도 있다

 

1번을 그림으로 풀어서 보면 아래와 같다. a, b일 때 a는 지훈이의 최단거리, b는 불의 최단거리이다.

---

1, 2	2, 1	3, 2
지훈	불	4, 1
1, 2	2, 1	3, 2

---

좌측 상단의 좌표를 행, 열 순으로 (0, 0)이라고 했을 때 (0, 0)일 때와 (2, 0)일 때 지훈이는 1분만에 도착, 불은 2분만에 도착하므로 지훈이는 불이 붙기 전에 해당 위치를 갈 수 있기 때문에 미로를 탈출할 수 있는 것이다.

 

불의 최단거리와 지훈이의 최단거리를 구하기 위해 각각 배열을 만들어주었다.

 

3번도 구현할 때 주의해야 한다 ⭐️⭐️

 

불이 2개 이상일 경우를 위해 배열의 원소를 초기화해줄 때 INF(무한대)로 해주어야 한다.

그리고 BFS를 돌며 만약 새로 구한 최단거리가 현재의 최단거리보다 작다면 갱신해주는 방식으로 진행해야 한다.

 

구현 1 - 틀렸습니다

부가 설명은 코드에서 주석으로 설명하겠다. 

#include <bits/stdc++.h>

using namespace std;

#define INF 987654321 // 무한대
#define MAX 1003 // R, C가 최대 1000이기 때문에 넉넉하게 1003으로 정의

int r, c; // 행, 열
string s; // 입력을 받을 때 사용하는 변수
char miro[MAX][MAX]; // 입력으로 들어온 미로
int jihoon[MAX][MAX]; // 지훈이의 최단거리를 저장
int fire[MAX][MAX]; // 불의 최단거리를 저장
int ret = INF; // 결과(가장 빠른 탈출시간)

// BFS를 위해 필요한 변수와 배열
int x, y, nx, ny;
int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};

queue<pair<int, int>> jq; // 지훈 BFS
queue<pair<int , int>> fq; // 불 BFS

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> r >> c;

    // 입력
    for (int i = 0; i < r; ++i) {
        cin >> s;
        for (int j = 0; j < c; ++j) {
            miro[i][j] = s[j];
            fire[i][j] = INF; // fire 초기화
            if (s[j] == 'J') jq.push({i, j}); // 지훈이 시작점 대입
            if (s[j] == 'F') {
                fq.push({i, j}); // 불 시작점 대입
                fire[i][j] = 0; // 시작점의 최단거리는 0
            }
        }
    }

    // 지훈이 BFS
    while(!jq.empty()) {
        x = jq.front().first;
        y = jq.front().second;
        jq.pop();

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

            if (nx >= 0 && nx < r && ny >= 0 && ny < c) { // index가 미로를 벗어나지 않았을 때
                if (miro[nx][ny] == '#') { // 벽은 최단거리 계산에 영향을 주지 않도록 무한대를 저장
                    jihoon[nx][ny] = INF;
                    continue;
                }

              	// 방문하지 않은 칸일 때
                if (jihoon[nx][ny] == 0) {
                    jihoon[nx][ny] = jihoon[x][y] + 1; // 최단거리를 계산
                    jq.push({nx, ny});
                }
            }
        }
    }

    // 불 BFS
    while(!fq.empty()) {
        x = fq.front().first;
        y = fq.front().second;
        fq.pop();

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

            if (nx >= 0 && nx < r && ny >= 0 && ny < c) { // index가 미로를 벗어나지 않았을 때
            	// 벽이거나 이미 방문한 칸이라면 skip
                if (miro[nx][ny] == '#' || fire[nx][ny] != INF) continue;

                fire[nx][ny] = min(fire[nx][ny], fire[x][y] + 1); // 최단거리를 계산
                fq.push({nx, ny});
            }
        }
    }

    for (int i = 0; i < r; ++i) {
        for (int j = 0; j < c; ++j) {
            // 미로의 가장자리에 도착했을 때
            if (i ==  0 || j == 0 || i == r-1 || j == c-1) {
                if (miro[i][j] == '#') continue; // 벽은 무시
                
                // 지훈이가 불보다 먼저 도착했다면 최단거리 계산
                if (fire[i][j] > jihoon[i][j]) ret = min(ret, jihoon[i][j]);
            }
        }
    }

    if (ret >= INF) { // 미로를 탈출할 수 없는 경우
        cout << "IMPOSSIBLE" << "\n";
    } else { // 미로를 탈출한 경우
    	// ret은 미로의 가장자리에 도착했을 때이므로
        // 1을 더했을 때가 탈출시간이다.
        cout << ret + 1 << "\n";
    }

    return 0;
}

반례

백준 질문게시판에서 반례를 찾을 수 있었다.

4 4
####
#J##
##F.
##.#

반례일 때 miro와 jihoon의 결과

반례에서 지훈이는 벽에 둘러싸여 있기 때문에 IMPOSSIBLE이 출력되어야 한다.

하지만 내가 적은 코드를 실행시키면 (2, 3)에서 지훈이의 최단거리가 0이 되기 때문에 결과가 1로 출력된다.

그러므로 jihoon 배열을 0으로 초기화시키면 안된다.

 

구현 2 - 맞았습니다!!

jihoon 배열을 최초에 -1로 초기화하도록 코드를 수정해주었다. 그 부분 말고는 구현 1 때와 코드가 동일하다.

#include <bits/stdc++.h>

using namespace std;

#define INF 987654321
#define MAX 1003

int r, c;
string s;
char miro[MAX][MAX];
int jihoon[MAX][MAX];
int fire[MAX][MAX];
int ret = INF;

int x, y, nx, ny;
int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};

queue<pair<int, int>> jq; // 지훈 BFS
queue<pair<int , int>> fq; // 불 BFS

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> r >> c;

    // 입력
    for (int i = 0; i < r; ++i) {
        cin >> s;
        for (int j = 0; j < c; ++j) {
            miro[i][j] = s[j];
            fire[i][j] = INF; // fire 초기화
            jihoon[i][j] = -1; // 수정한 부분 ‼️
            if (s[j] == 'J') {
                jihoon[i][j] = 0;
                jq.push({i, j}); // 지훈이 시작점
            }
            if (s[j] == 'F') {
                fq.push({i, j}); // 불 시작점
                fire[i][j] = 0;
            }
        }
    }

    // 지훈이 계산
    while(!jq.empty()) {
        x = jq.front().first;
        y = jq.front().second;
        jq.pop();

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

            if (nx >= 0 && nx < r && ny >= 0 && ny < c) {
                if (miro[nx][ny] == '#') {
                    continue;
                }

                // not visited
                if (jihoon[nx][ny] == -1) {
                    jihoon[nx][ny] = jihoon[x][y] + 1;
                    jq.push({nx, ny});
                }
            }
        }
    }

    // 불 계산
    while(!fq.empty()) {
        x = fq.front().first;
        y = fq.front().second;
        fq.pop();

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

            if (nx >= 0 && nx < r && ny >= 0 && ny < c) {
                if (miro[nx][ny] == '#' || fire[nx][ny] != INF) continue;

                fire[nx][ny] = min(fire[nx][ny], fire[x][y] + 1);
                fq.push({nx, ny});
            }
        }
    }

    for (int i = 0; i < r; ++i) {
        for (int j = 0; j < c; ++j) {
            // 미로의 가장자리에 도착
            if (i ==  0 || j == 0 || i == r-1 || j == c-1) {
                if (miro[i][j] == '#' || jihoon[i][j] == -1) continue;
                if (fire[i][j] > jihoon[i][j]) ret = min(ret, jihoon[i][j]);
            }
        }
    }

    if (ret >= INF) { // 미로를 탈출할 수 없는 경우
        cout << "IMPOSSIBLE" << "\n";
    } else {
        cout << ret + 1 << "\n";
    }

    return 0;
}

반례 모음

질문 게시판에 친절하신 분이 반례를 정리해준 글이 있다.

맞왜틀이라면 아래 글을 참고해보자 ~~

글 읽기 - 반례모음