[BaekJoon] 백준 4170번 불!

 

기존의 5427번 불 문제와 3055번 탈출 문제와 다른 점을 모르겠다.

 

 

 

이번 문제도 동일하게 풀었다.

 

VISIT을 값에 따라 나눠준다.

0 : 지나갈 수 있다

1 : 지훈이의 방문

2 : 불의 방문

3 : 벽

 

지훈이 같은 경우에는, 1 2 3의 위치는 방문하지 않는다. 이미 지나온 곳은 방문할 수 없으며, 불은 갈 수 없고, 벽은 갈 수 없기에.

불 같은 경우에는, 2 3의 위치는 방문하지 않는다. 불이 지나온 곳은 방문할 수 없으며, 벽은 방문할 수 없기에.

 

 

중요한 핵심은

불의 위치들을 우선 큐에 먼저 전부 넣어준 뒤, 마지막으로 지훈이의 위치를 큐에 넣어준다.

그리고 bfs를 시작하면 된다. 그럼 한 사이클의 bfs만으로 문제를 풀 수 있다.

 

 

"매 위치는 한 번만 방문하게 되고, 매 위치에서 고려는 상하좌우를 고려한다."

이는 일반적인 한 자리에서의 시작되는 최단거리 bfs와 시간복잡도가 결국 같다.

#include <iostream>
#include <vector>
#include <queue>

using namespace std;


char MAP[1000][1000];
int VISIT[1000][1000]; // 0 : 지나갈 수 있음, 1 : 지훈, 2 : 불, 3 : 벽
int DEPTH[1000][1000];

int N, M;
int J_x, J_y;

queue<pair<int, pair<int, int>>> que;

int mx[4] = {0, 0, -1, 1};
int my[4] = {1, -1, 0, 0};


int bfs() {
    
    
    while(!que.empty()) {
        
        int type = que.front().first;
        
        int x = que.front().second.first;
        int y = que.front().second.second;
        
        
        que.pop();
        
        
        for(int i = 0; i < 4; i++) {
            
            
            int tx = x + mx[i];
            int ty = y + my[i];
            
            
            switch (type) {
                case 1: // 지훈
                    
                    if(tx < 0 || tx >= N || ty < 0 || ty >= M)
                        return DEPTH[x][y] + 1; // 성공
                    
                    if(VISIT[tx][ty] == 0) { // 0인 곳만 지나다닐 수 있음.
                        que.push({1, {tx, ty}});
                        VISIT[tx][ty] = 1;
                        DEPTH[tx][ty] = DEPTH[x][y] + 1;
                    }
                    
                    break;
                    
                case 2: // 불
                    if(tx < 0 || tx >= N || ty < 0 || ty >= M)
                        continue;; // 다시

                    if(VISIT[tx][ty] < 2) { // 0과 1인 곳을 지나다닐 수 있음.
                        que.push({2, {tx, ty}});
                        VISIT[tx][ty] = 2;
                        
                    }
                    
                    
                    break;
            }
            
            
        }
        
    }
    return -1;
    
}

int main() {
    
    
    cin >> N >> M;
    
    
    for(int i = 0; i < N; i++) {
        for(int j = 0; j < M; j++) {
            cin >> MAP[i][j];
            
            if(MAP[i][j] == 'F') { // 불
                que.push({2, {i, j}});
                VISIT[i][j] = 2;
            }
            else if(MAP[i][j] == 'J') { // 지훈
                J_x = i; J_y = j;
            }
            else if(MAP[i][j] == '#') { // 벽
                VISIT[i][j] = 3;
            }
        }
    }
    
    que.push({1, {J_x, J_y}});
    VISIT[J_x][J_y] = 1;
    
    
    int V = bfs();
    
    if(V == -1)
        cout << "IMPOSSIBLE\n";
    else
        cout << V << "\n";
    
    
    
}

 

 

소요 시간 : 30분