[BFS/DFS] C11 백준 5427 불 풀이

문제

• 5427

풀이 과정

• 문제를 보면,
  • 불은 동서남북 방향으로 인접한 빈 공간으로 퍼져나간다. -> bfs 구나
  • 벽에는 불이 붙지 않는다. -> 좌표는 빈공간으로만 넓히면 되겠구나
  • 상근이는 동서남북 인접한 칸으로 이동할 수 있으며, 1초가 걸린다 -> 1턴에 갈 수 있는 곳은 동서남북 이구나
  • 상근이는 벽을 통과할 수 없고, 불이 옮겨진 칸 또는 이제 불이 붙으려는 칸으로 이동할 수 없다. -> 그럼 불보다 값이 적어야 갈 수 있으니까 불 bfs 먼저 돌려야 겠구나
• 4179 랑 같은 문제
  • 위의 문제를 풀었다면 어려울 게 없다! 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 w,h;
char map[MAX][MAX];
int visit_sg[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 < h && ny >= 0 && ny < w &&
                map[nx][ny] == '.' && visit_f[nx][ny] == 0) {
                visit_f[nx][ny] = visit_f[cur.x][cur.y] + 1;
                enqueue(nx, ny);
            }
        }
    }
}

int bfssg(int x, int y) {
    front = 0, rear = 0;
    
    visit_sg[x][y] = 1;
    enqueue(x, y);
    
    while (front < rear) {
        Q cur = dequeue();
        
        if (cur.x == 0 || cur.x == h-1 || cur.y == 0 || cur.y == w-1) {
            return visit_sg[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 < h && ny >= 0 && ny < w &&
                map[nx][ny] == '.' && visit_sg[nx][ny] == 0 &&
                (visit_f[nx][ny] == 0 || visit_f[nx][ny] > visit_sg[cur.x][cur.y] + 1)) {
                visit_sg[nx][ny] = visit_sg[cur.x][cur.y] + 1;
                enqueue(nx, ny);
            }
        }
    }
    return -1;
}

int main() {
    int tc;
    scanf("%d", &tc);
    
    while (tc--) {
        scanf("%d %d", &w, &h);
        
        front = 0;
        rear = 0;
        for (int i=0; i<h; i++) {
            for (int j=0; j<w; j++) {
                visit_sg[i][j] = 0;
                visit_f[i][j] = 0;
            }
        }
        
        for (int i=0; i<h; i++) {
            scanf("%s", map[i]);
        }
        
        int x = 0, y = 0;
        for (int i=0; i<h; i++) {
            for (int j=0; j<w; j++) {
                if (map[i][j] == '@') {
                    x = i;
                    y = j;
                } else if (map[i][j] == '*') {
                    visit_f[i][j] = 1;
                    enqueue(i ,j);
                }
            }
        }
        
        bfsfire();
        int result = bfssg(x, y);
        if (result == -1) {
            printf("IMPOSSIBLE\n");
        } else {
            printf("%d\n", result);
        }
    }
    return 0;
}