[BOJ/C++] 3055: 탈출

🏅 Gold 4

✏️ 1차 솔루션

1. 물의 위치를 queue 에 push
2. 물이 갈 수 있는 위치를 먼저 표시하고 이후에 고슴도치가 갈 수 있는 위치로 고슴도치 옮겨주기
   1) 위치를 옮겨서 탐색을 시작할 때마다 물 queue 에서 위치를 뽑아서 다음에 물이 갈 수 있는 위치에도 물 표시를 해주고 이는 새로운 물 위치이기 때문에 queue 에 push
   2) 고슴도치가 갈 수 있는 위치로 재귀
   ➡️ 고슴도치가 이동할 때는 이미 지나온 자리는 다시 돌아갈 수 없으므로 다음 위치로 이동하기 전에 현재 위치 board 값 'S' 로 표시
   ➡️ 다음 위치로 이동할 때마다 count
   ❗️ 이동한 위치가 비버집이면 return
   ❗️ 상하좌우 모두 이동할 수 없으면 count 값을 -1 로 표기

🚨 1차 trouble

계속 -1 이 출력됨
count 하는 방법이 비효율적인 것 같음
현재 방법으로는 고슴도치를 이동할 때, 물, X, 지나온 경로는 피할 수 있지만 최소 경로를 찾는 방법은 아닌 것 같음
탈출을 할 수 없는 경우에 대한 판단과 최종 count를 함수 return 으로 해야할지 변수로 해야할지 모르겠음

✏️ 최종 솔루션

⭐️ BFS 로 풀이 + DP 발상

• 각 자리에 대한 물의 거리와 고슴도치 거리 배열은 -1 로 초기화
• 고슴도치의 초기 위치와 물의 초기 위치만 0 으로 저장
  ➡️ 이렇게 되면 고슴도치와 물 모두 이미 방문한 곳은 0 이상이 됨
  ❗️ X나 비버 집처럼 아예 도달할 수 없는 영역에 대해서는 board 값으로 판단해줌
  ❗️ 비버 집 위치에 대한 고슴도치 거리나 물 거리는 계산할 필요 X ➡️ 어차피 물은 도달하지 못하고 고슴도치 거리의 경우, 고슴도치 위치로부터 상하좌우의 값을 활용해서 최종적으로 고슴도치가 비버집까지 도달하는데 걸리는 최단시간을 계산하기 때문

1. 각 자리에 대해 물이 도달하는 데 걸리는 거리(시간) 저장 ➡️ queue 사용
2. 각 자리에 대해 고슴도치가 도달하는 데 걸리는 거리(시간) 저장 ➡️ queue 사용
   ➡️ 이미 방문한 위치는 각 위치에 대한 고슴도치 이동 거리를 계산하면서 계산이 완료되었다면 방문했다고 판단 가능
3. 비버 집을 기준으로 상하좌우의 위치까지 고슴도치가 도달하는 데 걸리는 시간 중에 최소 시간을 최종적인 최단경로로 return
   ❗️ 이때, 해당 위치까지 고슴도치가 도달하는 데 걸리는 거리가 물이 도달하는 데 걸리는 거리보다 짧아야 갈 수 있는 위치라고 판정

📌 self feedback

1. BFS를 활용해서 풀이하는 점은 생각하지 못했는데 물의 위치를 queue 로 관리하는 것까지는 발상할 수 있었음
2. 기껏 물 거리와 고슴도치 거리를 계산해두고 또 DFS로 최단경로를 count 하는 멍청한 짓을 할 뻔했음
   ➡️ 어떻게 하면 기존 데이터, 자료형으로 써먹을 수 있을지 고민하는 과정이 필요

✏️ 최종 code

#include <iostream>
#include <queue>
#include <string>
#include <cstring>
using namespace std;

struct pos {
    int x;
    int y;
};

int r,c,sx,sy;
char board[51][51];
queue<pos> water;

int wdist[51][51];
int sdist[51][51];

// 상하좌우
int dx[4]={-1,1,0,0};
int dy[4]={0,0,-1,1};

void waterCheck() {
    while(!water.empty()) {
        pos p=water.front();
        int x=p.x;
        int y=p.y;
        
        for(int i=0;i<4;i++) {
            int nx=x+dx[i];
            int ny=y+dy[i];
            
            int cnt=wdist[x][y];
            if(nx<0 || nx>=r || ny<0 || ny>=c) continue;
            if(board[nx][ny]!='X' && board[nx][ny]!='D'&& wdist[nx][ny]==-1) {
                water.push({nx,ny});
                wdist[nx][ny]=cnt+1;
            }
        }
        water.pop();
    }
}

void sCheck() {
    queue<pos> q;
    q.push({sx,sy});
    sdist[sx][sy]=0;
    
    while(!q.empty()) {
        pos sp=q.front();
        int x=sp.x;
        int y=sp.y;
        
        int cnt=sdist[x][y];
        for(int i=0;i<4;i++) {
            int nx=x+dx[i];
            int ny=y+dy[i];
            
            if(nx<0 || nx>=r || ny<0 || ny>=c) continue;
            if (board[nx][ny]=='X' || board[nx][ny]=='D' || sdist[nx][ny]!=-1) continue;
            q.push({nx,ny});
            sdist[nx][ny]=cnt+1;
        }
        q.pop();
    }
}

int main() {
    int fx,fy;
    cin >> r >> c;
    
    memset(wdist,-1,sizeof(wdist));
    memset(sdist,-1,sizeof(sdist));
  
    for(int i=0;i<r;i++) {
        for(int j=0;j<c;j++) {
            cin >> board[i][j];
            if(board[i][j] == 'S') sx = i, sy = j;
            else if(board[i][j] == 'D') fx = i, fy = j;
            else if(board[i][j] == '*') {
                water.push({i,j});
                wdist[i][j]=0;
            }
        }
    }

    waterCheck();
    sCheck();

    int ans=30000;

    for (int i=0; i<4; i++) {
        int nx=fx+dx[i];
        int ny=fy+dy[i];

        if(nx<0 || nx>=r || ny<0 || ny>=c) continue;
        // 고슴도치가 더 늦게 도착할 경우이면서 물이 갈 수 있는 위치인 경우
        if(wdist[nx][ny] > 0 && sdist[nx][ny] >= wdist[nx][ny]) continue;
        // 고슴도치가 갈 수 없는 위치일 경우
        if(sdist[nx][ny] == -1) continue;
        ans=min(ans, sdist[nx][ny]+1);

    }

    if (ans==30000) cout << "KAKTUS";
    else cout << ans;
}