[BaekJoon/백준] 5427번 불

 

문제를 읽고, 최단시간을 말하니까 bfs로 풀어야겠다고 생각했고

 

그럼 문제의 이 조건의 상관관계를 어떻게 문제없이 해결할 수 있을까 생각하며 시뮬레이션을 해봤다.

 

그 결과, 큐에 불들을 먼저 넣어준 뒤에 마지막에 상근이의 위치를 넣고 bfs를 그상태에서 시작하며

 

상근이의 이동 고려시, 이미 불로 처리된 곳으로만 못가게 처리하면 되겠다는 생각이 들었다.

 

 

1. 큐에 불들의 좌표를 다 넣고, 상근이의 좌표를 넣은 뒤 bfs를 시작한다
2. VISIT값 0은 미방문이고, 1은 상근이고 2는 불이다.
3. 큐는 pair<int, pair<int, int>>인데, 이는 {type, {x, y}} 이다. type : 1은 상근이고 type : 2는 불이다.

 

 

코드는 길어도, 구현은 간단하니 이해하실 수 있을 것 같습니다.

/*
 
 시뮬레이션
 숫자는 시간을 의미
 a b 같은 알파벳은 불의 종류를 의미
 
 
 queue 과정 시뮬레이션
 
 1a 1b 1상근
 
 1b 1상근 2a 2a
 
 1상근 2a 2a 2b 2b
 
 2a 2a 2b 2b 2상근
 
 2a 2b 2b 2상근 3a 3a 3a
 
 
 
 불 먼저 큐에 놓고, 마지막에 상근이 놓고
 
 불은 상하좌우 퍼지게 계속 넣고,
 상근이는 상하좌우에 불이 있으면 못가고.
 
 
 */

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

using namespace std;

char MAP[1000][1000];
int VISIT[1000][1000];
 
int DEPTH[1000][1000]; // 상근이 것에 대한 데이터로만 따져주면 되겠다.

int sX, sY; // 상근이 좌표
vector<pair<int, int>> fire; // 불 좌표

queue<pair<int, pair<int, int>>> que; // 종류, x좌표, y좌표

int T, N, M;

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

int bfs() {
        
    
    while(!que.empty()) {
        
        int type = que.front().first; // 상근이 = 1, 불 = 2
        
        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(MAP[tx][ty] != '#' && VISIT[tx][ty] == 0) { // 왔던곳 1은 안가고, 불인 2는 안가니까, 0만 갈 수 있음
                        
                        que.push({1, {tx, ty}});
                        VISIT[tx][ty] = 1; // 상근이
                        DEPTH[tx][ty] = DEPTH[x][y] + 1;
                        
                        
                    }

                    break;
                    
                default: // 불
                    
                    if(tx < 0 || tx >= N || ty < 0 || ty >= M)
                        continue; // 불이 맵 벗어나는것은 방지.
                    
                    if(MAP[tx][ty] != '#' && VISIT[tx][ty] != 2) { // 왔던곳 2만 아니면 갈 수 있음.
                        que.push({2, {tx, ty}});
                        VISIT[tx][ty] = 2; // 불
                    }
                    
                    break;
            }
            
        }
        
    }
    
    return -1; // 탈출 못함
    
}

int main() {
    
    cin >> T;

    
    while(T--) {
        
        memset(VISIT, 0, sizeof(VISIT));
        memset(DEPTH, 0, sizeof(DEPTH));
        
        while(!que.empty()) que.pop();
        while(!fire.empty()) fire.pop_back();
        
        cin >> M >> N;
        
        for(int i = 0; i < N; i++) {
            for(int j = 0; j < M; j++) {
                
                cin >> MAP[i][j];
                
                if(MAP[i][j] == '*')
                    fire.push_back({i, j});
                else if(MAP[i][j] == '@') {
                    sX = i; sY = j;
                }
                    
            }
        }
        
        
        int FS = fire.size();
        
        for(int i = 0; i < FS; i++) {
            que.push({2, fire[i]});
            VISIT[fire[i].first][fire[i].second] = 2; // fire 경로 = 2
        }
        
        que.push({1, {sX, sY}});
        VISIT[sX][sY] = 1; // 사람경로 = 1
        
        
        
        int V = bfs();
        
        if(V == -1)
            cout << "IMPOSSIBLE\n";
        else
            cout << V << "\n";
        
    }

}

 

 

한번에 깔끔하게 잘 푼 것 같다.

 

 

소요 시간 : 40분