[BFS/DFS] C11 백준 4197 불! 풀이

문제

• 4179

풀이 과정

• 불은 각 지점에서 네 방향으로 확산된다 -> bfs가 떠오르는군.
• 지훈이는 미로의 가장자리에 접한 공간에서 탈출할 수 있다 -> bfs 종료 조건
• 문제에서 지훈이는 입력이 1개라고 말해줬지만...
  • 예제 입력보고 당연히 불도 1개인줄 알고 enqueue조건을 F 1개만 바라보고 썼다가 호되게 틀려버렸다(ㅠㅠ)
  • 불은 여러 개 일 수 있다는 가정하에 풀어야 함
• 지훈이는 이미 불이 붙은쪽으로는 갈 수 없음
  • 불 bfs 한 번 돌리고, 불 bfs에 따른 값을 보고 갈지 안갈지 결정하는 조건 필요
• BFS 사용, 자료구조는 큐

#include <stdio.h>

#define MAX 1001

typedef struct Que {
    int x;
    int y;
} Q;

int dx[4] = {0, 0, -1, 1};
int dy[4] = {1, -1, 0, 0};

int r,c;
char map[MAX][MAX];
int visit_j[MAX][MAX];
int visit_f[MAX][MAX];

Q que[MAX*MAX];
int front;
int rear;

void enqueue(int x, int y) {
    que[rear].x = x;
    que[rear].y = y;
    rear++;
}

Q dequeue() {
    return que[front++];
}

void bfsfire() {
    while (front < rear) {
        Q cur = dequeue();
        
        for (int i=0; i<4; i++) {
            int nx = cur.x + dx[i];
            int ny = cur.y + dy[i];
            
            if (nx >= 0 && nx < r && ny >= 0 && ny < c &&
                map[nx][ny] == '.' && visit_f[nx][ny] == -1) {
                visit_f[nx][ny] = visit_f[cur.x][cur.y] + 1;
                enqueue(nx, ny);
            }
        }
    }
}

int bfsjh(int x, int y) {
    front = 0;
    rear = 0;
    
    visit_j[x][y] = 1;
    enqueue(x, y);
    
    while (front < rear) {
        Q cur = dequeue();
        
        if (cur.x == r-1 || cur.y == c-1 || cur.x == 0 || cur.y == 0) {
            return visit_j[cur.x][cur.y];
        }
        
        for (int i=0; i<4; i++) {
            int nx = cur.x + dx[i];
            int ny = cur.y + dy[i];
            
            if (nx >= 0 && nx < r && ny >= 0 && ny < c &&
                map[nx][ny] == '.' && visit_j[nx][ny] == -1 &&
                (visit_f[nx][ny] == -1 || visit_j[cur.x][cur.y] + 1 < visit_f[nx][ny])) {
                    visit_j[nx][ny] = visit_j[cur.x][cur.y] + 1;
                    enqueue(nx, ny);
            }
        }
    }
    return -1;
}

int main() {
    scanf("%d %d", &r, &c);
    for (int i=0; i<r; i++) {
        scanf("%s", map[i]);
    }
    
    for (int i=0; i<r; i++) {
        for (int j=0; j<c; j++) {
            visit_f[i][j] = -1;
            visit_j[i][j] = -1;
        }
    }
    
    int x = 0;
    int y = 0;
    for (int i=0; i<r; i++) {
        for (int j=0; j<c; j++) {
            if (map[i][j] == 'F') {
                visit_f[i][j] = 1;
                enqueue(i, j);
            } else if (map[i][j] == 'J') {
                x = i;
                y = j;
            }
        }
    }
    
    bfsfire();
    int result = bfsjh(x, y);
    if (result == -1) {
        printf("IMPOSSIBLE");
    } else {
        printf("%d", result);
    }
    
    return 0;
}