(C++) - 백준(BOJ) 5427번 : 불

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

5427번: 불

bfs 구현 문제였습니다.

 

풀이방법

매 테스트케이스마다 적절히 입력을 받고 초기화를 한 다음을 시행합니다. 

 1. 불이 갈 수 있는 지점까지의 거리가 곧 해당 지점이 타는 시간초입니다. 따라서 불이 각 지점에 퍼지는 시간초를 bfs를 시행하며 visitedFire배열에 저장합니다. bfs를 시행하는 도중 만약 다음지점이 빌딩 밖이라면 현재 지점은 탈출할 수 있는 구역이므로 행,열 좌표를 저장하는 구조체 Coord로 이루어진 vector 변수 escapeCoords에 저장됩니다.

 

 2. 상근 또한 bfs를 통해 각 지점에 도착하는 시간들을 구할 수 있습니다. 이를 visited배열에 저장합니다. 마찬가지로 escapeCoords에 탈출할 수 있는 행,열 좌표들을 저장해줍니다.

 

 3.  안전한 탈출경로인지 확인하고 안전하면 상근이와 탈출가능한 지점의 거리들 중 최소값을 ans변수에 저장합니다.

탈출경로의 길이가 상근이가 더 짧으면 안전합니다. 

 

 4. ans에 적절한 값이 있다면 정답을 출력합니다. ans가 갱신되지 않았다면 탈출할 수 없는 경우이므로 IMPOSSIBLE을 출력합니다.

 

* 불은 여러개일 수 있습니다.

* 상근이는 바로 탈출할 수도 있습니다. 

* 탈출할 수 있는 루트도 여러곳일 수 있습니다. 그 중 가장 빨리 탈출하는 곳이 답입니다.

 

Code

#include <bits/stdc++.h>
using namespace std;
using pii = pair<int,int>;
int dx[4] = {0, 0, -1, 1};
int dy[4] = {-1, 1, 0, 0};
int visited[1001][1001];
int fireVisited[1001][1001];
int w,h,t,r,c;
struct Coord { int r, c; };
vector <Coord> fireCoords, escapeCoords;

void fireBFS(string building[1001]){
    queue <pii> q;
    for(auto f : fireCoords) q.push({f.r,f.c}),fireVisited[f.r][f.c] = 0;
    while(!q.empty()){
        int x = q.front().first;
        int y = q.front().second;
        q.pop();
        for(int i = 0; i < 4; i++){
            int nx = x + dx[i];
            int ny = y + dy[i];
            if(0 > nx || nx >= h || 0 > ny || ny >= w) {
                if(building[x][y] == '.' || building[x][y] == '@') {
                    Coord c = {x,y};
                    escapeCoords.push_back(c);
                }
                continue;
            }
            if(building[nx][ny] =='#' || fireVisited[nx][ny] != -1) continue;
            fireVisited[nx][ny] = fireVisited[x][y] + 1;
            q.push({nx,ny});
        }
    }
}


void bfs(string building[1001]){
    queue <pii> q;
    q.push({r,c});
    visited[r][c] = 0;
    while(!q.empty()){
        int x = q.front().first;
        int y = q.front().second;
        q.pop();
        for(int i = 0; i < 4; i++){
            int nx = x + dx[i];
            int ny = y + dy[i];
            if(0 > nx || nx >= h || 0 > ny || ny >= w) { 
                if(building[x][y] == '.' || building[x][y] == '@') escapeCoords.push_back({x,y});
                continue; 
            }
            if(building[nx][ny] =='#' || visited[nx][ny] != -1) continue;
            visited[nx][ny] = visited[x][y] + 1;
            q.push({nx,ny});
        }
    }
}

bool isSafe(int escapeRow, int escapeCol){
    if(escapeRow == -1 || escapeCol == -1) return false;
    if(visited[escapeRow][escapeCol] == -1) return false;
    if(visited[escapeRow][escapeCol] >= fireVisited[escapeRow][escapeCol] && fireVisited[escapeRow][escapeCol] != -1) {
        return false;
    }
    return true;
}

int main(){
    cin >> t;
    while(t--){
        int ans = 0x3f3f3f3f;
        memset(visited,-1,sizeof(visited));
        memset(fireVisited,-1,sizeof(fireVisited));
        fireCoords.clear();
        escapeCoords.clear();
        string building[1001];
        cin >> w >> h;
        for(int i = 0; i < h; i++){
            cin >> building[i];
            for(int j = 0; j < w; j++){
                if(building[i][j] == '@') r = i, c = j;
                if(building[i][j] == '*') fireCoords.push_back({i,j});
            }
        }
        fireBFS(building);
        bfs(building);
        for(auto e : escapeCoords){
            if(isSafe(e.r,e.c)) ans = min(ans,visited[e.r][e.c] + 1);
        }
        if(ans == 0x3f3f3f3f) cout << "IMPOSSIBLE\n";
        else cout << ans << '\n';
    }
}

 

Test Case

 질문 게시판의 반례를 직접 작성해 보았습니다. 

 

1
7 4
###.###
#.....#
#@....#
*######
답 : 5

1
3 3
..#
#@#
###
답 : 2

2
2 2
@*
..
4 4
####
@..#
*#..
*###

답:
1
1

1
4 3
####
#*.@
####
답 : 1

1
3 3
###
#@.
##*
답 : IMPOSSIBLE

21
1 1
@
3 3
.#.
#@#
.#.
3 3
...
.@.
...
3 3
.#.
#@#
.#*
8 3
########
#*@.....
########
5 6
##.##
#...#
#.#.#
#.#@#
#*#.#
#####
5 6
##.##
#...#
#.#.#
#*#@#
#.#.#
#####
5 6
##.##
#...#
#*#.#
#.#@#
#.#.#
#####
8 9
########
#......#
#.####.#
#.#@.#.#
#.##.#.#
#....#.#
######.#
.......#
########
5 3
##.##
#*.@#
#####
7 7
.......
.*#.##.
.##.##.
...@...
.##.##.
.##.#*.
.......
7 7
......*
.##.##.
.##.##.
...@...
.##.##.
.##.##.
*......
7 7
.*....*
.##.##.
.##.##.
...@...
.##.##.
.##.##.
.*....*
7 7
.......
*##.##*
.##.##.
...@...
.##.##.
.##.##.
*.....*
7 7
*....*.
.##.##.
.##.##.
...@...
.##.##.
.##.##.
*....*.
7 7
*.....*
.##.##.
.##.##.
...@...
.##.##.
*##.##*
.......
7 7
..#.#..
.*#.#*.
.##.##.
...@...
.##.##.
.*#.#*.
.......
7 7
.......
.*#.#*.
.##.###
...@...
.##.###
.*#.#*.
.......
7 7
.......
.*#.#*.
###.##.
...@...
###.##.
.*#.#*.
.......
7 7
.......
.*#.#*.
.##.##.
...@...
.##.##.
.*#.#*.
..#.#..
5 3
..#..
.@#*.
..#..

답:
1
IMPOSSIBLE
2
IMPOSSIBLE
6
5
IMPOSSIBLE
IMPOSSIBLE
28
IMPOSSIBLE
IMPOSSIBLE
IMPOSSIBLE
4
4
4
4
4
4
4
4
2

1
5 6
##.##
#...#
#.#.#
#.#@#
#*#.#
#####
답 : 5