백준(C++) 4179 [불!]

 

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

불 4179

접근방법

BFS 문제중 하나이다. 테스트 케이스 만큼의 입력이 주어지고, 입력으로 그래프의 너비 w와 높이 h가 주어진다. 

여기에 문제에서 주어진 기호를 넣어 하나의 테스트 케이스 문을 완성한다. 기호는 다음과 같다.

시작위치는 하나만 주어진다.

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

이를 보면 단순하게 테스트 케이스 만큼 반복을 해주고,  BFS 입력 큐에 @의 좌표를 입력후 BFS를 돌려주면된다.

BFS 조건은 지훈이는 동서남북 1번씩 이동 및 벽, 불 통과 불가능 이다. 

다른 문제와 다른점이라면 지훈이가 1번이동하면 불도 인근으로 번질수 있다는것이다.

이러한 특징때문에 이 문제를 풀때 매우 애먹었다. 지훈이와 불의 BFS를 동시에 처리할수있는 방법이 마땅히 생각이 안났기때문이다. 

그래서 여러 사람들의 글을 참고한 결과 처음 생각한 방법인 한곳에 다 밀어넣고 동시에 BFS 하는게 아니고

일단 한개의 BFS를 돌리고 바뀐 위치에 시간의 정보를 입력하고, 다른 BFS를 돌리는 것이다.

그렇기에 지훈이와 불중에 처음 돌릴 BFS를 골라야하는데 지훈이의 이동은 불의 영향을 받기에 불을 먼저 돌리기로 했다.

그후 지훈이의 BFS에 시간에 따른 불의 위치에 따라 이동할수 있는가 없는가를 조건에 추가하면된다.

정작 써보니 단순한 방법인데 너무 복잡하게 생각한 것 같다.

 

코드는 다음과 같다.

 

#include<iostream>
#include<queue>
using namespace std;
    string board[1002];
    int is[1002][1002];
    int is2[1002][1002];
    int xx,yy; 
    int x[4] = {1 ,0 ,-1, 0};
    int y[4] = {0 ,1 , 0 ,-1};
    

    int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> xx >> yy;
    
    queue<pair<int, int> > q;
    queue<pair<int, int> > q2;

    for(int a=0;a<xx;a++)
            cin >> board[a];

            for(int a=0;a<xx;a++){
            fill(is[a],is[a]+yy,-1); //string 채우기
            fill(is2[a],is2[a]+yy,-1);
            }

            for(int a=0;a<xx;a++){
                for(int b=0;b<yy;b++){

            if(board[a][b] == 'F'){
            q.push({a,b}); // 지훈이 시작 위치
            is[a][b] = 0;
            }
            if(board[a][b] == 'J'){
             q2.push({a,b}); // 불 시작 위치
             is2[a][b] = 0;}
             }
              }

               
                
            while(!q.empty()){ // 불 BFS
                auto cur = q.front(); q.pop();
                for(int dir =0; dir < 4;dir++){
                    int nx = cur.first+x[dir];
                    int ny = cur.second+y[dir];
                    if(nx < 0 || nx >=xx || ny < 0 || ny >= yy) continue; //범위 벗어남
                    if(is[nx][ny] >= 0 || board[nx][ny] == '#') continue; // -1,1 일때 
                    is[nx][ny] = is[cur.first][cur.second]+1; // 거리 + 1
                    q.push({nx,ny});
                   
                    
                }
            }


                    
            while(!q2.empty()){ // 지훈이 BFS
                auto cur = q2.front(); q2.pop();
                for(int dir =0; dir < 4;dir++){
                    int nx = cur.first+x[dir];
                    int ny = cur.second+y[dir];
                    if(nx < 0 || nx >=xx || ny < 0 || ny >= yy){ //범위 벗어남 탈출 성공
                        cout << is2[cur.first][cur.second]+1 ;
                        return 0;
                    }
                    if(is2[nx][ny] >= 0 || board[nx][ny] == '#') continue; // -1,1 일때 
                    if(is[nx][ny] <= is2[cur.first][cur.second]+1 && is[nx][ny] != -1)continue;
                    is2[nx][ny] = is2[cur.first][cur.second]+1; // 거리 + 1
                    q2.push({nx,ny});
                    
                    }
     
                }
                cout << "IMPOSSIBLE";
            }