백준 4179 - 불! (C++)

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

 

풀이과정

지훈이가 불을 피해서 미로의 가장자리로 이동할 수 있는지 판단하는 문제이다.먼저 불을 전부 확산시키고 지훈이가 이동할 수 있는지 확인할 수 있도록 bfs를 2번 실행시키면 해결할 수 있다. 

! 주의할 점으로, 매번 불을 확산시키고 지훈이가 이동 가능한지 확인하는 것을 반복하면 시간초과가 발생한다.

최대 arr[1000][1000] 배열에서 bfs를 50~100번 정도 실행하면 1초를 넘길 수 있기 때문이다.

풀이

1. 먼저 불을 확산시키며 위치마다 몇분이 걸리는지도 확인한다.

불은 여러곳에 존재할 수 있기 때문에 deque에 전부 넣어놓고 bfs를 실행하여 visited 배열에 걸리는 시간을 저장한다.

void fireMap() {
    // 불 확산
    int y,x,ny,nx;
    while(!fireq.empty()) {
        y = fireq.front().first;
        x = fireq.front().second;
        fireq.pop_front();

        for(int i=0; i<4; i++) {
            ny = y + dy[i];
            nx = x + dx[i];
            if(ny >= R || ny < 0 || nx >= C || nx < 0) continue;
            if(maze[ny][nx] == 1 || visited[ny][nx]) continue;
            visited[ny][nx] = visited[y][x] + 1;
            fireq.push_back({ny,nx});
        }
    }
}

 

2. 지훈이가 매 분 마다 이동하며, 불이 없는 곳 또는 불이 확산된 곳의 시간보다 먼저 도착할 수 있다면 이동해가며 bfs를 실행한다.

int solution() {
    int y,x,depth;
    int ny,nx;
    while(!escapeq.empty()) {
        y = escapeq.front().y;
        x = escapeq.front().x;
        depth = escapeq.front().minute;
        escapeq.pop_front();

        // 끝부분 도착
        if(y == R-1 || y == 0 || x == C-1 || x == 0) {
            return depth;
        }

        for(int i=0; i<4; i++) {
            ny = y + dy[i];
            nx = x + dx[i];
            if(maze[ny][nx] == 1 || moved[ny][nx] == 1) continue;
            // 이동 가능
            if(visited[ny][nx] == 0 || visited[ny][nx] > depth+1) {
                escapeq.push_back({ny,nx,depth+1});
                moved[ny][nx] = 1;
            }
        }
    }
    return -1;
}

 

! 지훈이가 이미 탈출한 상태일 수 있기 때문에 입력할 때 미리 체크해놓아야 한다.

 

코드

#include <iostream>
#include <stdio.h>
#include <memory.h>
#include <deque>
using namespace std;

int R,C;
int maze[1000][1000];
int visited[1000][1000];
int moved[1000][1000];
int dy[4] = {-1,1,0,0};
int dx[4] = {0,0,-1,1};
deque < pair < int,int > > fireq;
typedef struct option {
    int y,x,minute;
}op;
deque < op > escapeq;

void fireMap() {
    // 불 확산
    int y,x,ny,nx;
    while(!fireq.empty()) {
        y = fireq.front().first;
        x = fireq.front().second;
        fireq.pop_front();

        for(int i=0; i<4; i++) {
            ny = y + dy[i];
            nx = x + dx[i];
            if(ny >= R || ny < 0 || nx >= C || nx < 0) continue;
            if(maze[ny][nx] == 1 || visited[ny][nx]) continue;
            visited[ny][nx] = visited[y][x] + 1;
            fireq.push_back({ny,nx});
        }
    }
}

int solution() {
    int y,x,depth;
    int ny,nx;
    while(!escapeq.empty()) {
        y = escapeq.front().y;
        x = escapeq.front().x;
        depth = escapeq.front().minute;
        escapeq.pop_front();

        // 끝부분 도착
        if(y == R-1 || y == 0 || x == C-1 || x == 0) {
            return depth;
        }

        for(int i=0; i<4; i++) {
            ny = y + dy[i];
            nx = x + dx[i];
            if(maze[ny][nx] == 1 || moved[ny][nx] == 1) continue;
            // 이동 가능
            if(visited[ny][nx] == 0 || visited[ny][nx] > depth+1) {
                escapeq.push_back({ny,nx,depth+1});
                moved[ny][nx] = 1;
            }
        }
    }
    return -1;
}

int main() {
    int result = -1;
    string s;
    scanf("%d %d",&R,&C);
    for(int i=0; i<R; i++) {
        cin >> s;
        for(int j=0; j<C; j++) {
            if(s[j] == '#') maze[i][j] = 1;
            else if(s[j] == 'F') {
                fireq.push_back({i,j});
                visited[i][j] = 1;
            }
            else if(s[j] == 'J') {
                // 이미 탈출해있을 경우
                if(i == R-1 || i == 0 || j == C-1 || j == 0) {
                    result = 0;
                }
                escapeq.push_back({i,j,1});
                moved[i][j] = 1;
            }
        }
    }
    if(result == 0) {
        printf("1\n");
        return 0;
    }
    fireMap();
    result = solution();
    (result == -1) ? printf("IMPOSSIBLE\n") : printf("%d\n",result);
}