백준 3055 탈출 - 확산하는 물체가 2개 있을때 bfs를 돌려야 한다면?

문제 링크

www.acmicpc.net/problem/3055

풀이 아이디어

최단경로 문제이므로 당연히 BFS를 이용해서 풀어야 한다. 

문제는 확산하는 물체가 고슴도치 1개와 물 n개라는 것이다.

 

구체적으로 푸는 방식은 여러개가 있을 수 있다. 나는 bfs 함수를 하나만 정의했지만 

물이 이동하는 bfs, 고슴도치가 이동하는 bfs 함수를 각각 짜서 비교해보며 진행을 해도 된다.

하지만 각 객체(고슴도치,물) 이 확산하는 정보는 따로 관리가 들어가야 하므로

queue는 2개를 반드시 이용해 주어야 한다.

 

나는 queue 2개를 이용을 하되, 함수를 하나만 정의 했다.

문제의 조건에 따라 물을 먼저 이동시키고, 그 이후에 고슴도치를 이동시키기.

 

추가적으로 사용한 2가지 팁은

1. for문을 이용해 큐의 사이즈만큼 물, 고슴도치 이동을 시키기

2. int visited 배열을 이용해 방문 여부와 시간을 동시에 체크하기

코드

#include <bits/stdc++.h>
using namespace std;

int dx[4] = {1,-1,0,0};
int dy[4] = {0,0,1,-1};
int r,c;
pair<int,int> start,destination;
queue<pair<int,int>> water;
char a[51][51];
int answer=-1;
int visited[51][51];

void bfs(){
    queue<pair<int,int>> q;
    q.push(start);
    visited[start.first][start.second]=1;
    while(!q.empty()){
        //물을 차오르게 함.
        int watersize = water.size();
        

        for(int i=0; i<watersize; i++){
            int curx = water.front().first;
            int cury = water.front().second;
            water.pop();
            for(int j=0; j<4; j++){
                int nx = curx + dx[j];
                int ny = cury + dy[j];
                if(nx<0 || nx >=r || ny<0 || ny>=c)
                    continue;
                if(a[nx][ny]=='.'){
                    a[nx][ny]='*';
                    water.push({nx,ny});
                }
            }
        }


        int cursize = q.size();
        for(int i=0; i<cursize; i++){
            int x = q.front().first;
            int y = q.front().second;
            q.pop();
            if(x==destination.first && y==destination.second){
                answer = visited[x][y]-1;
                return;
            }
            for(int j=0; j<4; j++){
                int nx = x+dx[j];
                int ny = y+dy[j];
                if(0<=nx && nx<r && 0<=ny && ny<c){
                    if(visited[nx][ny]==0 && a[nx][ny]!='*' && a[nx][ny]!='X'){
                        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++){
            cin>>a[i][j];
            if(a[i][j]=='D'){
                destination = {i,j};
            }
            else if(a[i][j]=='S'){
                start = {i,j};
            }
            else if(a[i][j]=='*'){
                water.push({i,j});
            }

        }
    }
    bfs();
    if(answer==-1)
        cout<<"KAKTUS";
    else
        cout<<answer;
}