[백준]13549번. 숨바꼭질3

[문제]

 

www.acmicpc.net/problem/13549

13549번: 숨바꼭질 3

 

[풀이]

 

언니의 위치 N, 동생의 위치 K가 입력으로 주어지고 언니가 동생을 찾는데 걸리는 최소 시간을 구하는 문제이다.

숨바꼭질4( www.acmicpc.net/problem/13913) 와 굉장히 유사한 문제이다.

 

 

BFS를 사용해서 풀었다. 

원래 BFS는 방문 체크를 하여 이미 방문한 곳이라면 다시 방문하지 않는다.

하지만 이 문제에서는 순간이동이 있으므로 이미 방문했더라도 최솟값을 가질 수 있다.

 

ex) 5 --> 8

1. 5-> 6-> 7-> 8  : 3초

2. 5-> 10-> 9-> 8  : 2초

 

따라서 이미 방문했더라도 현재 이동 횟수가 더 작다면 재방문 할 수 있도록 하였다.

이와 같은 방식으로 while문을 반복하여 K에 도착하면 map의 값을 return 하면서 BFS 함수를 끝내도록 하였다.

 

 

[코드]

 

시간 : 0ms

 

#include <iostream>
#include <queue>

#define MAX 200001

using namespace std;

int map[MAX]={0,};
int N,K;

int dx[2]={-1,1};

int BFS()
{
    queue <int> q;
    q.push(N);
    map[N]=1;
    
    while(!q.empty()){
        
        int x = q.front();
        q.pop();
        
        if(x == K)  return map[x]-1;
        
        for(int i=0;i<3;i++){
            int npos = x;
            if(i==2)    npos = x*2;
            else    npos= x+dx[i];
            
            if(npos <0 || npos >= MAX)  continue;
            if(i!=2 &&  (map[npos]!=0 && map[npos] <= map[x]+1))    continue;
            if(i==2 &&  (map[npos]!=0 && map[npos] <= map[x]))  continue;
            
            q.push(npos);
            
            if(i==2)    map[npos] = map[x];
            else    map[npos]= map[x]+1;
        }
    }
    
    return 0;
}
int main(void)
{
    cin >> N>> K;
    cout << BFS();
}