[백준] 3055. 탈출

[문제]

 

www.acmicpc.net/problem/3055

3055번: 탈출

[풀이]

 

고슴도치가 비버의 굴로 이동해야 하는데 물이 있거나 돌이 있는 곳으로는 움직일 수 없다.

물은 매 분마다 인접한 곳으로 퍼진다. 단 , 비버가 존재하는 곳이나 돌이 존재하는 곳으로는 퍼질 수 없다.

이 때 최단 거리를 구하는 문제.

 

고슴도치의 이동경로를 저장하는 visited 배열과 물, 돌의 정보를 저장하는 map을 선언했다.

BFS 함수의 while 문에서 물이 먼저 퍼지고 그 다음에 고슴도치가 움직이도록 하였다.

물은 move 함수를 통해서 퍼지고 물이 있는 곳의 좌표를 vector water에 저장하였다.

 

다음으로 BFS를 사용해 고슴도치가 비버의 굴로 가는데 최단 거리를 구했다.

고슴도치가 이미 방문한 곳이라면 최단 거리를 구하는 문제이므로 continue를 걸어줬다.

또한 이미 물이 차있거나 돌이 존재하는 곳이라면 지나가지 못하므로 마찬가지로 continue를 걸어줬다.

 

이렇게 BFS를 사용해 고슴도치의 최단거리를 구할 수 있었다.

또한 BFS 함수가 끝나고 visited 배열에서 도착 지점 좌표의 값이 0이라면 고슴도치가 갈 수 없는 경우이므로 'KAKTUS'를 출력하도록 했다.

 

 

 

[코드]

 

시간 : 0ms

 

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

#define MAX 51

using namespace std;

struct pos{
    int x,y;
};

pos S,D; // 고슴도치, 비버

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

int visited[MAX][MAX]={0,};
int map[MAX][MAX]={0,};
int R,C;


vector <pos> water;

void move()
{
    int size = water.size();
    
    for(int i=0;i<size;i++)
    {
        int x= water[i].x;
        int y= water[i].y;
        
        for(int j=0;j<4;j++){
            int nx=x+dx[j];
            int ny=y+dy[j];
            
            if(nx < 0 || ny<0 || nx >= R || ny >= C || map[nx][ny] != 0) continue;
            else if( nx == D.x && ny == D.y)  continue;

            map[nx][ny]=1;
            water.push_back({nx,ny});
            
        }
    }
}

void BFS()
{
    queue <pos> q;
    q.push({S.x,S.y});
    int cnt =-1;
    
    while(!q.empty()){

        int x = q.front().x;
        int y = q.front().y;
        q.pop();
        
        if(cnt != visited[x][y]){
            move();
            cnt= visited[x][y];
         }
        if( x == D.x && y == D.y)  return;
            
        
        for(int i=0;i<4;i++){
            
            int nx = x+dx[i];
            int ny = y+dy[i];
            
            if(nx < 0 || ny<0 || nx >= R || ny >= C || visited[nx][ny] != 0) continue;
            else if(map[nx][ny] != 0)   continue;
            
            q.push({nx,ny});
            visited[nx][ny] = visited[x][y]+1;
            
        }
    }

}

int main(void)
{
    cin >> R >> C;
    
    for(int i=0;i<R;i++){
        for(int j=0;j<C;j++){
            char ch1;
            cin >> ch1;
            
            if(ch1 == '.')  map[i][j]=0;
            else if(ch1 == '*'){
                map[i][j]=1; //물
                water.push_back({i,j});
            }
            else if (ch1 == 'X')    map[i][j]=-1; // 돌
            else if(ch1 == 'S') S={i,j};
            else if(ch1 == 'D') D={i,j};
            
        }
    }
    
    BFS();
    if(visited[D.x][D.y] == 0)    cout<<"KAKTUS";
    else cout << visited[D.x][D.y];
    
    return 0;
    
}