[알고리즘] 백준 4179

백준 4179번 불!

해결 과정 요약

불을 bfs를 이용해 visited배열에 최단거리를 저장하면서 확산시켜준다.
그 후에 사람이 bfs를 이용해 go배열에 최단거리를 저장하면서 이동을 시작하는데 아래와 같은 조건을 추가하여 벽이거나 불이 있다면 이동하지 않는다.

if(ny < 0 || nx < 0 || ny >= N || nx >= M || m[ny][nx] < 0) continue;
if(visited[ny][nx] == 0){
	visited[ny][nx] = visited[y][x] + 1;
	q.push({ny, nx});
}
else if(visited[ny][nx] > visited[y][x] + 1){
	visited[ny][nx] = visited[y][x] + 1;
	q.push({ny, nx});
}

가장자리에 도달하면 flag를 1로 만들어주고 결과값을 출력한다.
프로그램이 종료되기 전 flag가 0이라면 IMPOSSIBLE을 출력한다.

풀이

#include <bits/stdc++.h>
using namespace std;

int N,M,sy,sx,flag;
string s;
int m[1004][1004];
int visited[1004][1004];
int go[1004][1004];
int dy[] = {-1, 0, 1, 0};
int dx[] = {0, 1, 0, -1};

void fire(int ay, int ax){
    queue<pair<int,int>> q;
    visited[ay][ax] = 1;
    q.push({ay, ax});
    while(!q.empty()){
        int y; int x;
        tie(y, x) = q.front(); q.pop();
        for(int i=0; i<4; i++){
            int ny = y + dy[i];
            int nx = x + dx[i];
            if(ny < 0 || nx < 0 || ny >= N || nx >= M || m[ny][nx] < 0) continue;
            if(visited[ny][nx] == 0){
                visited[ny][nx] = visited[y][x] + 1;
                q.push({ny, nx});
            }
            else if(visited[ny][nx] > visited[y][x] + 1){
                visited[ny][nx] = visited[y][x] + 1;
                q.push({ny, nx});
            }
        }
    }
}

void escape(){
    queue<pair<int,int>> q;
    go[sy][sx] = 2;
    q.push({sy, sx});
    while(!q.empty()){
        int y; int x;
        tie(y, x) = q.front(); q.pop();
        if(y == 0 || x == 0 || y == N-1 || x == M-1){
            cout << go[y][x] - 1 << "\n";
            flag = 1;
            return;
        }
        for(int i=0; i<4; i++){
            int ny = y + dy[i];
            int nx = x + dx[i];
            if(ny < 0 || nx < 0 || ny >= N || nx >= M || m[ny][nx] < 0) continue;
            if(go[ny][nx] == 0){
                if(visited[ny][nx] == 0){
                    go[ny][nx] = go[y][x] + 1;
                    q.push({ny, nx});
                }
                else if(visited[ny][nx] >= go[y][x] + 1){
                    go[ny][nx] = go[y][x] + 1;
                    q.push({ny, nx});
                }
            }
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    cin >> N >> M;
    for(int i=0; i<N; i++){
        cin >> s;
        for(int j=0; j<M; j++){
            if(s[j] == 'J') { sy = i; sx = j; }
            else if(s[j] == 'F') m[i][j] = 1;
            else if(s[j] == '#') m[i][j] = -1;
            else m[i][j] = 10000;
        }
    }
    
    for(int i=0; i<N; i++){
        for(int j=0; j<M; j++){
            if(m[i][j] == 1) fire(i, j);
        }
    }
    
    escape();
    if(flag == 0)
        cout << "IMPOSSIBLE\n";
    
    return 0;
}

코멘트

코드재사용이 많지만 어쩔수 없는듯