C - [백준 4179] 불! (feat. 이중 BFS)

참고 포스트

2024.12.25 - [Computer Science/자료구조 & 알고리즘] - C - [Backjoon 2178] 미로탐색 (feat. BFS & 최단거리 탐색)

C - [Backjoon 2178] 미로탐색 (feat. BFS & 최단거리 탐색)

참고 포스트https://rnasterofmysea.tistory.com/47 C - [Backjoon 1260] DFS와 BFS[참고 포스트]https://rnasterofmysea.tistory.com/45 [자료구조 & 알고리즘] 그래프 + DFS그래프에 대해 기초부터 차근차근 학습해보겠습니

rnasterofmysea.tistory.com

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

아래는 [BOJ 4179] 불! 문제의 설명과 코드 해설입니다. 블로그 형식에 맞춰 작성했습니다.

[BOJ 4179] 불!

문제 설명

BOJ 4179 문제는 R×CR \times C 크기의 격자에서 **불(F)**과 **지훈(J)**이 움직이며, 지훈이가 격자를 탈출하는 최소 시간을 구하는 문제입니다. 격자의 각 칸은 다음과 같은 값을 가집니다:

'#': 벽, 불과 지훈 모두 통과할 수 없음.
'.': 빈 공간, 불과 지훈이 이동 가능.
'F': 불의 초기 위치.
'J': 지훈이의 초기 위치.

문제 조건

불의 확산:
- 불은 매초 상하좌우로 확산하며, 벽(#)이나 이미 불이 있는 칸(F)으로는 확산하지 않습니다.
지훈이의 이동:
- 지훈이는 매초 상하좌우로 이동할 수 있으며, 불이 이미 방문한 칸이나 벽(#)으로는 이동할 수 없습니다.
- 지훈이가 격자 밖으로 나가면 탈출에 성공합니다.
탈출 실패:
- 지훈이가 더 이상 이동할 수 없고, 탈출하지 못한 경우 IMPOSSIBLE을 출력합니다.

입력

첫 번째 줄: R (행의 수)와 C (열의 수) (1≤R,C≤1000).
다음 R개의 줄: 격자의 상태를 나타내는 문자열.

출력

지훈이가 탈출하는 데 걸리는 최소 시간을 출력합니다.
탈출할 수 없는 경우 IMPOSSIBLE을 출력합니다.

입출력 예시

입력 1:

4 4
####
#JF#
#..#
#..#

출력 1:

입력 2:

4 4
####
#JF#
#..#
####

출력 2:

IMPOSSIBLE

Checkpoint

미로탐색(https://rnasterofmysea.tistory.com/51) 문제와 동일한 알고리즘 흐름이기 때문에 미로탐색을 했다면 크게 어려울 것이 없는 문제입니다. 다른 점은 불과 지훈에 대한 이중 BFS 처리가 필요하다는 점입니다 ( queue, visited 배열과 enqueue, deqeue 함수 등등 bfs 구현에 필요한 요소가 각 2개씩)

BFS는 그 전 문제와 동일하게 한칸씩 이동하면서 최단거리를 계산하는 역할을 합니다. 지훈이(J)와 불(F)은 각 한개씩밖에 존재하지 않으므로 j_bfs의 시작지점을 지훈이의 위치, f_bfs의 시작지점을 불의 위치로 설정하면 됩니다.

프로그램 종료조건이 2가지 입니다.

1. 지훈이의 현재 위치가 격자 범위(R, C) 밖으로 나가는 경우.

처리 방법:
- BFS 탐색 중에 지훈이의 현재 위치가 격자의 범위를 벗어나는지 확인.
- 이 조건을 만족하면 탈출에 성공한 것으로 간주하고, 현재까지 걸린 시간을 반환.
코드 예시:

// 탈출 조건
if (nx < 0 || nx >= R || ny < 0 || ny >= C) {
    return j_visited[x][y]; // 현재까지 걸린 시간 반환
}

이유:
- 지훈이가 격자 밖으로 나가는 순간 탈출 성공으로 간주되며, BFS 탐색을 더 이상 진행할 필요가 없습니다.
- 이 조건이 가장 먼저 처리되므로, 지훈이가 불보다 빠르게 격자를 벗어난 경우가 우선적으로 계산됩니다.

2. 지훈이가 길의 끝까지 가지 못하고 불을 만날 수밖에 없는 경우

종료 조건: 지훈이가 더 이상 이동할 수 없는 상태가 되거나, 이동 가능한 모든 경로에서 불이 먼저 도달한 경우.
처리 방법:
1. BFS 탐색을 통해 불의 확산 시간을 먼저 계산.
2. 지훈이가 이동 가능한 칸에서 불이 도달한 시간과 지훈이가 도달한 시간을 비교.
  - 지훈이가 불보다 빠르게 도달한 경우: 지훈이가 해당 칸으로 이동.
  - 불이 지훈이보다 빠르게 도달하거나 이미 도달한 경우: 해당 경로 차단.
3. BFS 탐색을 종료한 후에도 탈출 조건을 만족하지 못했다면, IMPOSSIBLE 출력.
코드 예시:

// 이동 조건
if (graph[nx][ny] == '.' && j_visited[nx][ny] == 0 &&
    (f_visited[nx][ny] == 0 || j_visited[x][y] + 1 < f_visited[nx][ny])) {
    j_visited[nx][ny] = j_visited[x][y] + 1;
    enqueue(j_queue, &j_rear, nx, ny);
}

이유:
- 불의 확산을 먼저 계산한 후, 지훈이가 안전한 경로로만 이동하도록 함.
- BFS 탐색 특성상, 불과 지훈이의 이동 경로를 시간 순서대로 계산하기 때문에 최적의 경로를 보장합니다.

+ 전체 로직에서 '.'가 들어왔을 때만 다음 과정을 처리하기 때문에 '#'에 대한 처리를 할 필요가 없습니다.

문제 풀이

BFS(너비 우선 탐색):
- 불과 지훈의 이동을 각각 BFS를 통해 처리합니다.
- 불은 먼저 확산하며, 각 칸에 도달하는 시간을 기록합니다.
- 지훈이는 BFS를 통해 탈출 가능한 칸을 탐색하며, 불이 도달하기 전에 도달할 수 있는 칸만 이동합니다.
탐색 순서:
- BFS는 불이 먼저 확산한 후, 지훈이가 이동하도록 합니다.
- 불의 확산 시간을 f_visited 배열에 기록하여 지훈이 이동 가능 여부를 판단합니다.
탈출 조건:
- 지훈이가 격자 밖으로 나가면 탈출 성공.
- 이동 가능한 모든 칸을 탐색했음에도 탈출하지 못하면 IMPOSSIBLE 출력.

구현 코드

#include <stdio.h>
#include <stdlib.h>
/*
https://www.acmicpc.net/problem/4179
BOJ 4179 불!
*/

#include <stdio.h>
#include <stdlib.h>

#define INF 1000000

// 전역 변수 선언
char graph[1000][1000];
int j_visited[1000][1000];
int f_visited[1000][1000];
int j_queue[1000000][2];
int f_queue[1000000][2];
int j_front = 0, j_rear = 0;
int f_front = 0, f_rear = 0;
int dir[4][2] = {{0, 1}, {0, -1}, {-1, 0}, {1, 0}};

// 큐 삽입
void enqueue(int queue[][2], int *rear, int x, int y) {
    queue[*rear][0] = x;
    queue[*rear][1] = y;
    (*rear)++;
}

// 큐 제거
void dequeue(int queue[][2], int *front, int *x, int *y) {
    *x = queue[*front][0];
    *y = queue[*front][1];
    (*front)++;
}

// 불의 BFS
void fire_bfs(int R, int C) {
    while (f_front < f_rear) {
        int x, y;
        dequeue(f_queue, &f_front, &x, &y);

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

            if (nx >= 0 && nx < R && ny >= 0 && ny < C && graph[nx][ny] == '.' && f_visited[nx][ny] == 0) {
                f_visited[nx][ny] = f_visited[x][y] + 1;
                enqueue(f_queue, &f_rear, nx, ny);
            }
        }
    }
}

// 지훈이의 BFS
int jihun_bfs(int R, int C) {
    while (j_front < j_rear) {
        int x, y;
        dequeue(j_queue, &j_front, &x, &y);

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

            // 탈출 조건
            if (nx < 0 || nx >= R || ny < 0 || ny >= C) {
                return j_visited[x][y];
            }

            // 이동 조건
            if (graph[nx][ny] == '.' && j_visited[nx][ny] == 0 && (f_visited[nx][ny] == 0 || j_visited[x][y] + 1 < f_visited[nx][ny])) {
                j_visited[nx][ny] = j_visited[x][y] + 1;
                enqueue(j_queue, &j_rear, nx, ny);
            }
        }
    }

    return -1; // 탈출 불가능
}

int main() {
    int R, C;
    scanf("%d %d", &R, &C);

    // 입력 및 초기화
    for (int i = 0; i < R; i++) {
        scanf("%s", graph[i]);
        for (int j = 0; j < C; j++) {
            if (graph[i][j] == 'J') {
                enqueue(j_queue, &j_rear, i, j);
                j_visited[i][j] = 1;
            }
            if (graph[i][j] == 'F') {
                enqueue(f_queue, &f_rear, i, j);
                f_visited[i][j] = 1;
            }
        }
    }

    // BFS 실행
    fire_bfs(R, C);
    int result = jihun_bfs(R, C);

    if (result == -1) {
        printf("IMPOSSIBLE\n");
    } else {
        printf("%d\n", result);
    }

    return 0;
}

1. 주요 변수

graph:
- 격자의 상태를 저장하는 배열.
- 값은 다음과 같습니다:
  - '#': 벽, 불과 지훈 모두 통과할 수 없음.
  - '.': 빈 공간, 불과 지훈 모두 이동 가능.
  - 'F': 불의 초기 위치.
  - 'J': 지훈의 초기 위치.
f_visited:
- 불의 방문 여부를 기록하는 배열.
- f_visited[x][y]: 불이 해당 칸에 도달한 시간을 저장.
j_visited:
- 지훈의 방문 여부를 기록하는 배열.
- j_visited[x][y]: 지훈이 해당 칸에 도달한 시간을 저장.
f_queue와 j_queue:
- BFS 탐색에 사용되는 큐.
- 각각 불과 지훈의 위치를 저장.

2. 불의 BFS (fire_bfs)

void fire_bfs(int R, int C) {
    while (f_front < f_rear) {
        int x, y;
        dequeue(f_queue, &f_front, &x, &y);

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

            if (nx >= 0 && nx < R && ny >= 0 && ny < C && graph[nx][ny] == '.' && f_visited[nx][ny] == 0) {
                f_visited[nx][ny] = f_visited[x][y] + 1;
                enqueue(f_queue, &f_rear, nx, ny);
            }
        }
    }
}

동작 원리:

BFS를 통해 불이 확산할 수 있는 모든 칸을 탐색하며, 각 칸에 불이 도달하는 최소 시간을 기록.
방문 여부는 f_visited 배열로 관리하며, 방문한 칸은 다시 탐색하지 않음.

3. 지훈이의 BFS (jihun_bfs)

int jihun_bfs(int R, int C) {
    while (j_front < j_rear) {
        int x, y;
        dequeue(j_queue, &j_front, &x, &y);

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

            // 탈출 조건
            if (nx < 0 || nx >= R || ny < 0 || ny >= C) {
                return j_visited[x][y];
            }

            // 이동 조건
            if (graph[nx][ny] == '.' && j_visited[nx][ny] == 0 && (f_visited[nx][ny] == 0 || j_visited[x][y] + 1 < f_visited[nx][ny])) {
                j_visited[nx][ny] = j_visited[x][y] + 1;
                enqueue(j_queue, &j_rear, nx, ny);
            }
        }
    }

    return -1; // 탈출 불가능
}