[BOJ G4][C++] 백준 4179번: 불!

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

4179번: 불!

 

문제

지훈이는 미로에서 일을 한다. 지훈이를 미로에서 탈출하도록 도와주자!

미로에서의 지훈이의 위치와 불이 붙은 위치를 감안해서 지훈이가 불에 타기전에 탈출할 수 있는지의 여부, 그리고 얼마나 빨리 탈출할 수 있는지를 결정해야한다.

지훈이와 불은 매 분마다 한칸씩 수평또는 수직으로(비스듬하게 이동하지 않는다)  이동한다. 

불은 각 지점에서 네 방향으로 확산된다. 

지훈이는 미로의 가장자리에 접한 공간에서 탈출할 수 있다. 

지훈이와 불은 벽이 있는 공간은 통과하지 못한다.

입력

입력의 첫째 줄에는 공백으로 구분된 두 정수 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1000 이다. R은 미로 행의 개수, C는 열의 개수이다.

다음 입력으로 R줄동안 각각의 미로 행이 주어진다.

 각각의 문자들은 다음을 뜻한다.

• #: 벽
• .: 지나갈 수 있는 공간
• J: 지훈이의 미로에서의 초기위치 (지나갈 수 있는 공간)
• F: 불이 난 공간

J는 입력에서 하나만 주어진다.

 

풀이

BFS 문제인데 이걸 응용해서 두번 돌려야하는 그런 문제였다.

 

불의 도달시간을 표시하는 BFS를 한번 돌리고,

그걸 바탕으로 시간에 따른 지훈이의 위치를 BFS 로 돌리면 된다.

 

이때 지훈이의 BFS 를 돌릴 때 조건을 추가했다

 

(1) 미로의 크기를 벗어나면 탈출로 간주하고 알고리즘 종료

// 미로 탈출시 종료
if(x<0 || x>=r || y<0 || y>=c) {
	cout << jihun[current.first][current.second] + 1;
    	return 0;
    }

 

(2) 지훈이가 가려는 곳에 이미 불이 있다면, 즉 가려는 타이밍보다 먼저 불이 붙었다면 지나가지 못함

// 가려는 곳에 불이 이미 있다면 (혹은 벽이라면) 패스
if(fire[x][y] != -1 && jihun[current.first][current.second] + 1 >= fire[x][y]) continue;

나는 여기서 `fire[x][y] != -1` 조건을 안넣었다가

"71%에서 틀렸습니다"

가 떠서 애먹었다... 불이 아예 가지 않은 부분도 생각했어야 했다.

 

아무튼 결론은 성공

 

코드

// Authored by : seondal
// 풀이 : https://whkakrkr.tistory.com/
// Co-authored by : -

//#include <bits/stdc++.h>
#include <iostream>
#include <queue>

using namespace std;

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

queue<pair<int, int>> q;
queue<pair<int, int>> s;

char board[1001][1001];
int fire[1001][1001];
int jihun[1001][1001];

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    // 입력 받기
    int r,c;
    cin >> r >> c;
    for(int i=0; i<r; i++){
        for(int j=0; j<c; j++){
            cin >> board[i][j];
            
            fire[i][j] = -1;
            jihun[i][j] = -1;
            
            if(board[i][j] == 'F'){
                q.push({i,j});
                fire[i][j] = 0;
            }
            if(board[i][j] == 'J') {
                s.push({i,j});
                jihun[i][j] = 0;
            }
        }
    }
    
    // 시간에 따른 불의 위치
    while(!q.empty()){
        pair<int, int> current = q.front();
        q.pop();
        
        for(int dir=0; dir<4; dir++){
            int x = current.first + dx[dir];
            int y = current.second + dy[dir];
            
            if(x<0 || x>=r || y<0 || y>=c) continue;
            if(fire[x][y] >= 0 || board[x][y] == '#') continue; // 이미 불이 있거나 벽이라면 패스
            
            fire[x][y] = fire[current.first][current.second] + 1;
            q.push({x,y});
        }
    }
    
    // 시간에 따른 지훈이의 위치
    while(!s.empty()) {
        pair<int, int> current = s.front();
        s.pop();
        
        for(int dir=0; dir<4; dir++){
            int x = current.first + dx[dir];
            int y = current.second + dy[dir];
            
            // 미로 탈출시 종료
            if(x<0 || x>=r || y<0 || y>=c) {
                cout << jihun[current.first][current.second] + 1;
                return 0;
            }
            
            // 이미 방문했거나 벽이 있으면 패스
            if(jihun[x][y] >= 0 || board[x][y] == '#') continue;
            
            // 가려는 곳에 불이 이미 있다면 (혹은 벽이라면) 패스
            if(fire[x][y] != -1 && jihun[current.first][current.second] + 1 >= fire[x][y]) continue;
            
            jihun[x][y] = jihun[current.first][current.second] + 1;
            s.push({x,y});
        }
    }
    
    // 탈출 실패
    cout << "IMPOSSIBLE";
    return 0;
}

/*
 */