[BOJ/3055번탈출] c++ / BFS

문제

고슴도치가 물을 피해 비버의 굴로 이동할 수 있는 가장 빠른 시간을 구하는 문제

- .은 비어있음 | * 물 | X 돌 | D 비버 굴 | S 고슴도치 위치

- 1분마다 고슴도치와 물은 상하좌우 인접한 칸으로 이동가능 

 

생각

물이 찰 예정인 곳에는 고슴도치가 이동하지 못함

처음 시작시 물이 있는 곳이랑 고슴도치가 있는 곳을 푸쉬해줌

동시에 탐색하면서 답을 구함
반례 

3 4
.D.*
X.S.
X*..
answer=KAKTUS

를 통해 반복문 두개 써서 물이랑 고슴도치 위치 따로 푸쉬해줘야 한다는 것을 깨달음!

문제풀이

1.큐를 생성

1-1.물이 있는 곳을 찾아 모두 큐에 푸쉬 + 방문표시 ( -1로 표현해줌 )

1-2.고슴도치가 있는 곳을 찾아 큐에 푸쉬 + 방문표시 ( 1로 표현해줌 / 이동할 때마다 +1 해줌 )

**물이 먼저 확장되기 때문에 하나의 반복문 안에서 두개를 동시에 찾아서 큐에 넣으면 안됨

( ex. *S* S** 이런식으로 큐에 들어가면 문제와는 다르게 실행됨 )

-> 따로따로 반복문 써서 구해야 됨 ( ex. **S *S 처럼 S가 큐의 마지막에 담겨야 함 )

2.BFS 탐색

3.기준칸이 물이 있는 칸이면

3-1.상하좌우에 방문표시가 없고 비어있는 곳이 나온다면, 방문표시(-1) + 큐에 푸쉬

4.기준칸이 고슴도치가 있는 칸이면

4-1.상하좌우에 방문표시가 없고 비어있는 곳이 나온다면, 방문표시(기준칸+1) + 큐에 푸쉬

4-2.상하좌우에 고슴도치 굴이 나온다면, 방문표시(기준칸 + 1) + 큐에 푸쉬

5.고슴도치 굴이 나온다면 vis[고슴도치 굴]-1 반환

6.도착하지 못한다면 -1 반환

7.result = -1이면, "KAKTUS"

7-1.아니면, 반환값 출력

 

 

코드

#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
#define X first
#define Y second
int dx[4] = {0, 0, -1, 1};
int dy[4] = {1, -1, 0, 0};
string board[51];
int R, C;
int vis[51][51];
int BFS() {
    queue<pair<int, int>> Q;

    for ( int i = 0; i < R; i++ )
        for ( int j = 0; j < C; j++ ) {
            if ( board[i][j] == '*' ) {
                vis[i][j] = -1;
                Q.push({i, j});
            }
        }

    for ( int i = 0; i < R; i++ )
        for ( int j = 0; j < C; j++ ) {
            if ( board[i][j] == 'S' ) {
                vis[i][j] = 1; // 고슴도치 시작 위치
                Q.push({i, j});
            }
        }

    while (!Q.empty()) {
        pair<int, int> cur = Q.front(); Q.pop();
        
        if ( board[cur.X][cur.Y] == 'D' )
            return vis[cur.X][cur.Y]-1;

        for ( int dir = 0; dir < 4; dir++ ) {
            int nx = cur.X + dx[dir];
            int ny = cur.Y + dy[dir];

            if ( nx < 0 || nx >= R || ny < 0 || ny >= C ) continue;

            if ( vis[cur.X][cur.Y] > 0 && ( board[nx][ny] == '.' || board[nx][ny] == 'D' ) && vis[nx][ny] == 0 ) {
                vis[nx][ny] = vis[cur.X][cur.Y] + 1;
                Q.push({nx, ny});
            }

            if ( vis[cur.X][cur.Y] == -1 && board[nx][ny] == '.' && vis[nx][ny] == 0 ) {
                vis[nx][ny] = -1;
                Q.push({nx, ny});
            }
        }
    }
    return -1;
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> R >> C;
    for ( int i = 0; i < R; i++ ) 
        cin >> board[i];
    
    int result = BFS();
    if ( result == -1 )
        cout << "KAKTUS\n";
    else
        cout << result << "\n";
}