[백준 - 4179] 불! - C++

분류: 시작점이 두 종류인 bfs, bfs 순차 실행 /

 

문제

문제 링크

문제 설명

지훈이는 미로에서 일을 한다. 지훈이를 미로에서 탈출하도록 도와주자!

미로에서의 지훈이의 위치와 불이 붙은 위치를 감안해서 지훈이가 불에 타기 전에 탈출할 수 있는지의 여부, 그리고 얼마나 빨리 탈출할 수 있는지를 결정해야 한다.

지훈이와 불은 매 분마다 한 칸씩 수평 또는 수직으로(비스듬하게 이동하지 않는다) 이동한다.

불은 각 지점에서 네 방향으로 확산된다.

지훈이는 미로의 가장자리에 접한 공간에서 탈출할 수 있다.

지훈이와 불은 벽이 있는 공간은 통과하지 못한다.

입력

입력의 첫째 줄에는 공백으로 구분된 두 정수 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1000이다. R은 미로 행의 개수, C는 열의 개수이다.

다음 입력으로 R줄동안 각각의 미로 행이 주어진다.

각각의 문자들은 다음을 뜻한다.

• #: 벽
• .: 지나갈 수 있는 공간
• J: 지훈이의 미로에서의 초기위치 (지나갈 수 있는 공간)
• F: 불이 난 공간

J는 입력에서 하나만 주어진다.

출력

지훈이가 불이 도달하기 전에 미로를 탈출할 수 없는 경우 IMPOSSIBLE을 출력한다.

지훈이가 미로를 탈출할 수 있는 경우에는 가장 빠른 탈출시간을 출력한다.

 

풀이

- 내 풀이(불 BFS -> 시간 기록 -> 지훈 BFS)

#include <iostream>
#include <queue>
#include <string>
using namespace std;
#define X first
#define Y second

string maze[1000];
int times[1000][1000];
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};

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

    int R, C;
    cin >> R >> C;
    queue<pair<int,int>> Q;
    pair<int, int> J;
    for(int i=0; i<R; i++) {
        cin >> maze[i];
        for(int j=0; j<C; j++) {
            if(maze[i][j] == 'F') Q.push({i, j});
            else {
                times[i][j] = -1;
                if(maze[i][j] == 'J') J = {i, j};
            }
        }
    }

    while(!Q.empty()) {
        auto cur = Q.front(); Q.pop();
        for(int d=0; d<4; d++) {
            int nx = cur.X + dx[d];
            int ny = cur.Y + dy[d];
            if(nx < 0 || nx >= R || ny < 0 || ny >= C) continue;
            if(maze[nx][ny] == '#') continue;
            if(times[nx][ny] != -1) continue;
            times[nx][ny] = times[cur.X][cur.Y] + 1;
            Q.push({nx, ny});
        }
    }

    times[J.X][J.Y] = 0;
    Q.push(J);
    while(!Q.empty()) {
        auto cur = Q.front(); Q.pop();
        int nxt = times[cur.X][cur.Y] + 1;
        for(int d=0; d<4; d++) {
            int nx = cur.X + dx[d];
            int ny = cur.Y + dy[d];
            if(nx < 0 || nx >= R || ny < 0 || ny >= C) {
                cout << nxt;
                return 0;
            }
            if(maze[nx][ny] == '#') continue;
            if(times[nx][ny] != -1 && times[nx][ny] <= nxt) continue;
            times[nx][ny] = nxt;
            Q.push({nx, ny});
        }
    }
    cout << "IMPOSSIBLE";
}

불 bfs를 돌며 불이 지나간 시간을 `times`에 기록

지훈 bfs를 돌며 불보다 먼저 도착했을 때만 이동

구현은 크게 세 부분으로 구성된다.

1. 입력을 받는 for문
   • 불은 시작점이 여러 개인 bfs로 불의 위치를 모두 큐에 넣고 bfs를 시작한다.
   • 지훈이의 위치는 나중에 bfs를 돌리기 위해 따로 저장해 둔다.
2. 불이 bfs 돌며 불이 지나간 시간을 기록
   • 범위 넘어가면 `continue`
   • 벽이면 `continue`
   • 이미 지나간 길(`times[nx][ny] != -1`)이라면 `continue`
3. 지훈이가 bfs 돌며 불보다 먼저 도착했을 때만 지나감
   • 범위 넘어가면 탈출
   • 벽이면 `continue`
   • 안 지나간 길(`times[nx][ny] == -1`) 이거나 불보다 먼저 지나가는 길(`nxt < times[nx][ny]`)일 경우 이동(push)

`times`는 불과 지훈이가 지나간 시간을 의미하며 -1은 아직 지나가지 않은 길이다.

불의 bfs에서 `times`는 이미 지나간 길을 다시 큐에 넣지 않기 위해 아직 안 지나간 길일 때만(`times[nx][ny] == -1`) 큐에 넣는다.

지훈이의 bfs에서 `times`는 아직 안 지나간 길(`times[nx][ny] == -1`)이거나 불보다 먼저 지나갈 때만(`nxt < times[nx][ny]`) 큐에 넣는다.

 

- 다른 사람 풀이(동시에 BFS, 스텝마다 멈춰서 확인 like generator function)

#include <iostream>
#include <queue>
using namespace std;

struct xy { int x, y; };

int R, C;
char maze[1000][1001]; // 널문자 고려
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
queue<xy> J, F;

void firesSpread() {
    int size = F.size();
    while(size--) {
        int x = F.front().x, y = F.front().y; F.pop();
        for(int i=4; i--;) {
            int nx = x + dx[i], ny = y + dy[i];
            if(nx < 0 || nx >= R || ny < 0 || ny >= C) continue;
            if(maze[nx][ny]=='#') continue;
            maze[nx][ny] = '#';
            F.push({nx, ny});
        }
    }
}

bool JihoonEscapes() {
    int size = J.size();
    if(size == 0) {
        cout << "IMPOSSIBLE";
        exit(0);
    }
    while(size--) {
        int x = J.front().x, y = J.front().y; J.pop();
        if(x == 0 || x == R-1 || y == 0 || y == C-1) return true;
        for(int i=4; i--;) {
            int nx = x + dx[i], ny = y + dy[i];
            if(nx < 0 || nx >= R || ny < 0 || ny >= C) continue;
            if(maze[nx][ny]=='#') continue;
            maze[nx][ny] = '#';
            J.push({nx, ny});
        }
    }
    return false;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    cin >> R >> C;
    for(int i=0; i<R; i++) {
        cin >> maze[i];
        for(int j=0; j<C; j++) {
            if(maze[i][j] == 'J') {
                J.push({i, j});
                maze[i][j] = '#';
            }
            else if(maze[i][j] == 'F') {
                F.push({i, j});
                maze[i][j] = '#';
            }
        }
    }

    int step = 0;
    do {
        firesSpread();
        step++;
    } while(!JihoonEscapes());
    cout << step;
}

# 널문자 고려

먼저 주의할 점은 `1 ≤ R, C ≤ 1000`일때 행은 상관없지만 열은 최대 1000글자 string으로 들어온다는 점이다.

1000글자 string은 널문자를 포함하여 최대 1001개의 저장공간이 필요하다.

`string maze[1000]`은 괜찮지만 `char maze[1000][1000]`은 `maze[i]`의 마지막(1001 번째) 널문자가 인접한 열의 첫번째 글자(`maze[i-1][0]`혹은 `maze[i+1][0]`)을 덮어쓸 수 있다는 점이다.

따라서 널문자를 고려해 `char maze[1000][1001]`로 받는다.

혹은 이중 for문에서 `cin >> maze[i][j]`로 받아야한다. 하지만 `char *`로 한번에 string으로 받는게 더 빠르다.

int maze[1000][1001]; // '\0' 고려
for(int i=0; i<R; i++) {
    cin >> maze[i]; // char* 로 한번에 string으로 받기
}

int maze[1000][1000];
for(int i=0; i<R; i++) {
    for(int j=0; j<C; j++) {
        cin >> maze[i][j]; // char 로 하나씩 받기
    }
}

 

# 벽으로 마킹

불 입장에서 지훈이에 독립적이고 불이 지나간 길은 벽과 같기 때문에 불이 지나간 길은 벽으로 마킹한다.

지훈이 입장에서 자신이 지나간 길과 불이 지나간 길은 벽과 같기 때문에 벽으로 마킹한다.

따라서 초기화와 bfs에서 지훈이와 불의 이동경로는 벽으로 마킹한다..

불은 지훈이에 독립적이고 지훈이는 불에 종속적이므로 불이 먼저 이동하고 지훈이가 이동해야 같은 시간에 도착했을 때 갈 수 없다는 것을 체크할 수 있다.

 

# BFS 순차 실행

`main`의 do-while문에서 불이 먼저 이동하고 지훈이가 이동한다.(윗 문단 마지막 줄 참고)

`JihoonEscapes`는 탈출 여부를 bool로 반환하여 탈출했다면 do-while문을 종료한다.

`step`은 bfs가 몇 사이클을 돌았는지 나타내며 조금 더 정확하게는 함수 `JihoonEscapes`의 호출 횟수를 나타낸다.

 

BFS를 generator function처럼 수행하는 것이 가능한 이유는 `firesSpread`와 `JihoonEscapes`에서 초기 큐의 사이즈로만 while을 돌기 때문이다.

int size = Q.size();
while(size--) {
    // push next generation
}

초기 큐로만 BFS를 수행하고 멈추기 때문에 함수의 시작과 끝에서 큐에는 같은 generation만 모여있다.

 

# exit(0)

지훈이가 더 이상 갈 수 있는 곳이 없을 경우 "IMPOSSIBLE"을 출력하고 프로그램을 종료해야 한다.

`main`에서는 `return 0`을 하면 되지만 다른 함수에서는 `exit(0)`으로 프로그램을 종료할 수 있다.

 

# 횟수가 주어진 반복문

n번 반복해야 하는 경우 `while(n--)`을 많이 사용한다. 하지만 이 방법은 n이 수정되어 n을 반복 횟수로만 사용할 때 사용한다.

for문은 루프에서 변수를 정의할 수 있다는 점을 이용해 n을 수정하지 않고 n회 반복하며 역순 인덱스를 사용할 수 있다.

// looping n times
for(int i=n; i--;) {
    // i: n-1 -> 0
}
for(int i=0; i<n; i++) {
    // i: 0 -> n-1
}
while(n--) {
    // n: n-1 -> 0
}