[백준][C++] 5427 불

www.acmicpc.net/problem/5427

5427번: 불

 

 

 

알고리즘 종류

    - BFS

    - 구현

 

 

 

사고 과정

    - 매 초마다, 사건은 두 가지가 동시에 일어난다.

        1. 불이 움직인다.

        2. 상근이가 움직인다.

 

    - 불이 있고, 또는 불이 움직일 곳으로는 상근이가 갈 수 없다. 그리고 상근이가 있는 칸에 불이 오는 동시에 상근이가 움직인다. 이를 구현하기 위해서는 동시간 대에 불이 먼저 움직이면 된다.

        * 0초

 

        * 1초

            + 왼쪽은 불이 먼저 움직인 사건이다. 동시간 1초대에서 빨간색은 불이 움직이 곳이고 노란색 이건 불이다.

            + 오른쪽은 상근이가 움직인 사건이다. 

 

        * 2초

            + 왼쪽은 불이 먼저 움직인 사건이다.

            + 오른쪽은 상근이가 움직인 사건이다. 하늘색의 상근이는 문제에서 '상근이가 있는 칸에 불이 옮겨옴과 동시에 다른 칸으로 이동할 수 있다.' 에 해당한다.

 

        * 정리하자면, 문제에서 제시된 조건을 충족하기 위해서는 동시간대에 불이 먼저 움직이고 상근이가 움직이면 된다. 알고리즘의 형태는 아래와 같이 된다.

while(조건){
 
    시간++;
 
    while(불의 Queue 크기){
        // 동작
    }
 
    while(상근의 Queue 크기){
        // 동작
    }
}
 

 

 

 

구현(C++)

#include <iostream>
#include <queue>
#include <cstring>
#define MAX 987654321
 
using namespace std;
 
 
int t, w, h;
 
char mat[1001][1001];
int sIsVisited[1001][1001];
int fIsVisited[1001][1001];
int dir[4][2] = {{1,0}, {0,1}, {-1,0}, {0,-1}};
 
queue<pair<int, int> > sq;
queue<pair<int, int> > fq;
 
bool isValid(int y, int x){
    return (y>=0 && y<h) && (x>=0 && x<w);
}
 
int bfs(){
 
    int time = 0;
    while(!sq.empty()){
        time++;
        
        // 불 이동  
        int fSize = fq.size();
        while(fSize--){
            int cy = fq.front().first;
            int cx = fq.front().second;
            fq.pop();
                
            for(int d=0; d<4; d++){
                int ny = cy + dir[d][0];
                int nx = cx + dir[d][1];
                    
                if(fIsVisited[ny][nx]) continue;
                if(!isValid(ny, nx)) continue;
                if(mat[ny][nx] == '#') continue;
                    
                fIsVisited[ny][nx] = 1;    
                fq.push({ny, nx});
            }    
        }
            
        // 상근이 이동  
        int sSize = sq.size();
        while(sSize--){
            int cy = sq.front().first;
            int cx = sq.front().second;
            sq.pop();
                
            for(int d=0; d<4; d++){
                int ny = cy + dir[d][0];
                int nx = cx + dir[d][1];
                    
                if(!isValid(ny, nx)) return time; // 상근이 탈출  
                    
                if(sIsVisited[ny][nx]) continue;
                if(mat[ny][nx] == '#') continue;
                if(fIsVisited[ny][nx]) continue;
                    
                sIsVisited[ny][nx] = 1;    
                sq.push({ny, nx});
            }
        }
    }
 
    return MAX;
}
 
 
int main(void){
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    
    cin >> t;
    
    while(t--){
        
        memset(fIsVisited, 0, sizeof(fIsVisited));
        memset(sIsVisited, 0, sizeof(sIsVisited));
        memset(mat, 0, sizeof(mat));
        while(!fq.empty()) fq.pop();
        while(!sq.empty()) sq.pop();
        
        cin >> w >> h;
        
        for(int i=0; i<h; i++){
            for(int j=0; j<w; j++){
                cin >> mat[i][j];
                if(mat[i][j] == '@'){
                    sq.push({i, j});
                    sIsVisited[i][j] = 1;
                } 
                if(mat[i][j] == '*') {
                    fq.push({i, j});
                    fIsVisited[i][j] = 1;
                }
            }
        }
        
        int res = bfs();
        if(res == MAX) cout << "IMPOSSIBLE" << endl;
        else cout << res << endl;
        
    }
}
 

 

 

 

시행착오

    - 목적지에 도착하면 바로 종료하고 값을 반환하면 되는데 본인은 한 바퀴 더 돌려서 시작점에서 반환하려고 하는 습관이 있었다. 그러면 중간에 목적지에 도착한 값이 한 바퀴를 돌 때 여러 조건들을 통과한다는 보장은 없다. 따라서 목적지에 도착하면 바로 답을 반환하자. 

 

    - 무슨 말인가...하면

아래와 같이 작성해야 되는데

while(sSize--){

            int cy = sq.front().first;

            int cx = sq.front().second;

            sq.pop();

                

            for(int d=0; d<4; d++){

                int ny = cy + dir[d][0];

                int nx = cx + dir[d][1];

                    

                if(!isValid(ny, nx)) return time; // 상근이 탈출  

                    

                if(sIsVisited[ny][nx]) continue;

                if(mat[ny][nx] == '#') continue;

                if(fIsVisited[ny][nx]) continue;

                    

                sIsVisited[ny][nx] = 1;    

                sq.push({ny, nx});

            }

}

 

아래와 같이 작성했었다.

// 상근이 이동  

        int sSize = sq.size();

        while(sSize--){

            int cy = sq.front().first;

            int cx = sq.front().second;

            sq.pop();

            

            if(!isValid(cy, cx)) return time; // 상근이 탈출  

                

            for(int d=0; d<4; d++){

                int ny = cy + dir[d][0];

                int nx = cx + dir[d][1];

                    

                if(sIsVisited[ny][nx]) continue;

                if(mat[ny][nx] == '#') continue;

                if(fIsVisited[ny][nx]) continue;

                    

                sIsVisited[ny][nx] = 1;    

                sq.push({ny, nx});

            }

        }