[백준/Baekjoon] 3055 탈출 C++ :: BFS

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

3055번: 탈출

---

1. Logic

고슴도치는 물로 찰 예정인 곳은 못가기 떄문에 고슴도치 이동보다 물 이동을 먼저 해줘야 한다. 

 

BFS두번 돌려주고 while(true)문 탈출하기 위해 옮겼는지만 확인해서 탈출만 잘 해주면 된다.

---

2. Code

#include <bits/stdc++.h>

using namespace std;

const int INF = 0x3f3f3f3f;

int r, c;

int sy, sx;
int goalY, goalX;

int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, -1, 0, 1};

char graph[101][101];
bool vis[101][101];

int bfs() {
    queue<pair<pair<int, int>, int>> kaktus;
    queue<pair<pair<int, int>, int>> kaktusTemp;
    queue<pair<int, int>> water;
    queue<pair<int, int>> waterTemp;
    
    for(int i = 0; i < r; i++) {
        for(int j = 0; j < c; j++) {
            if(graph[i][j] == '*') {
                water.push({i, j});
                vis[i][j] = true;
            }
        }
    }

    kaktus.push({{sy, sx}, 0});
    vis[sy][sx] = true;
    
    while(true) {
        bool check = false;
        
        while(!water.empty()) {
            int x = water.front().second;
            int y = water.front().first;

            water.pop();
            
            for(int i = 0; i < 4; i++) {
                int ny = y + dy[i];
                int nx = x + dx[i];
                
                if(nx < 0 || ny < 0 || nx >= c || ny >= r) continue;
                if(vis[ny][nx]) continue;
                if(graph[ny][nx] == 'X' || graph[ny][nx] == 'D') continue;
                
                vis[ny][nx] = true;
                waterTemp.push({ny, nx});
                check = true;
            }
        }
        
        while(!kaktus.empty()) {
            int x = kaktus.front().first.second;
            int y = kaktus.front().first.first;
            int cost = kaktus.front().second;
            
            kaktus.pop();
            
            if(x == goalX && y == goalY) {
                return cost;
            }
            
            for(int i = 0; i < 4; i++) {
                int ny = y + dy[i];
                int nx = x + dx[i];
                
                if(nx < 0 || ny < 0 || nx >= c || ny >= r) continue;
                if(vis[ny][nx]) continue;
                if(graph[ny][nx] == 'X' || graph[ny][nx] == '*') continue;
                
                vis[ny][nx] = true;
                kaktusTemp.push({{ny, nx}, cost+1});
                check = true;
            }
        }
        if(!check) break;
        water = waterTemp;
        kaktus = kaktusTemp;
    }
    
    return INF;
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    
    cin >> r >> c;
    
    for(int i = 0; i < r; i++) {
        for(int j = 0; j < c; j++) {
            cin >> graph[i][j];
            if(graph[i][j] == 'S') {
                sy = i;
                sx = j;
            }
            else if(graph[i][j] == 'D') {
                goalY = i;
                goalX = j;
            }
        }
    }
    
    int ans = bfs();

    if(ans == 0x3f3f3f3f) {
        cout << "KAKTUS";
    }
    else {
        cout << ans;
    }
}

알고리즘 Solve 후 제가 생각한 Logic을 기록하는 개인 공부 블로그입니다.
내용 중 최적화가 가능한 부분등은 언제든지 댓글로 틀린 부분 및 피드백 주시면 공부 및 반영하겠습니다🧐

728x90