[BaekJoon/백준] 3055번 탈출

문제를 읽는데,, 어제 푼 문제랑 너무 똑같다는 생각이 들었고, 정말 고민도 없이 곧바로 코딩을 시작한 뒤 풀 수 있었다.

 

어제 푼 골드4문제(5427번)와 똑같은 유형의 골드4문제였다.

 

풀이는 매우 똑같으니..! 풀이 설명은 해당 링크에 자세히 설명되어 있다!

 

 

물의 위치를 큐에 전부 먼저 넣어준 뒤에, 고슴도치의 위치를 넣어주고 그 다음에 bfs를 시작하면 된다.

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

using namespace std;

int N, M;

char MAP[50][50];
int VISIT[50][50]; // -1 : 소굴, 1 : 고슴도치, 2 : 물, 3 : 돌
int DEPTH[50][50]; // 도치의 움직임 depth

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

int SX, SY; // 고슴도치의 위치
int DX, DY; // 비버의 굴의 위치


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];
            
            if(tx < 0 || tx >= N || ty < 0 || ty >=M) // 맵 자체를 벗어나는 것들 방지
                continue;
            
            switch (type) {
                case 1: // 도치의 움직임. 도치가 왔던곳 = 1 && 물인곳 = 2 && 돌인곳 = 3 뺴고 가능 => 0보다 작을 경우 가능
                    
                    if(VISIT[tx][ty] <= 0) { // 미방문(0)이거나 || 소굴(-1)이거나
                        
                        que.push({1, {tx, ty}});
                        VISIT[tx][ty] = 1;
                        DEPTH[tx][ty] = DEPTH[x][y] + 1;
                        
                    }
                    
                    if(tx == DX && ty == DY) // 도착점인 소굴에 도착했다.
                        return DEPTH[tx][ty];
                    
                    break;
                    
                case 2: // 물의 움직임. 물이 왔던곳 == 2 && 돌인곳 == 3 && 소굴 == -1 빼고 가능 => 0이거나 1인경우 가능
                    
                    if(VISIT[tx][ty] == 0 || VISIT[tx][ty] == 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];
            
            
            switch(MAP[i][j]) {
                    
                case 'D': // 소굴
                    DX = i; DY = j;
                    VISIT[i][j] = -1;
                    break;

                case 'S': // 도치
                    SX = i; SY = j;
                    VISIT[i][j] = 1;
                    break;
                                        
                case '*':
                    water.push_back({i, j});
                    VISIT[i][j] = 2; // water
                    break;
                    
                case 'X':
                    VISIT[i][j] = 3; // ROCK
                    break;
            }
        }
    }
    
    
    
    int W_S = water.size();
    
    for(int i = 0; i < W_S; i++) // 물들 넣고
        que.push({2, {water[i].first, water[i].second}});
    
    // 도치찡 넣고
    que.push({1, {SX, SY}});
    
    
    
    int V = bfs();
    
    if(V == -1)
        cout << "KAKTUS\n";
    else
        cout << V << "\n";
}

 

한번에 깔끔하게 통과했다!

 

소요 시간 : 20분