[백준] 1697_ 숨바꼭질 / 그래프, 최단경로, BFS

 

 

Sliver

 

 

문제

 

수빈이는 동생과 숨바꼭질을 하고 있다.

수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 

수빈이는 걷거나 순간이동을 할 수 있다.

만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다.

순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다.

수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오.

 

 

입력

 

첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진다. N과 K는 정수이다.

 

 

출력

 

수빈이가 동생을 찾는 가장 빠른 시간을 출력한다.

 

 

---

 

풀이

 

import java.util.*;
import java.io.*;

class Main {
    static int N , M;
    static int[] check = new int[100001]; // 방문 여부와 이동 횟수를 저장하는 배열
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        
        int answer = bfs(N);
        
        System.out.println(answer);
    }

    public static int bfs(int node){
        Queue<Integer> q = new LinkedList<>();
        q.add(node);
        while(!q.isEmpty()){
            int index = q.poll();
            if(index == M) return check[index];
            
            // 한칸 뒤로 가는 경우
            if(index-1>=0 && check[index-1]==0){
                check[index-1]=check[index]+1;
                q.add(index-1);
            }
            
            // 한칸 앞으로 가는 경우
            if(index+1<=100000 && check[index+1]==0){
                check[index+1]=check[index]+1;
                q.add(index+1);
            }
            
            // 순간이동(2배이동) 하는 경우
            if(index*2<=100000 && check[index*2]==0){
                check[index*2]=check[index]+1;
                q.add(index*2);
            }
            
        }
		
        // M에 도달하지 못할 경우 -1 을 리턴
        return -1;
    }
}

 

 

해결방법

• check 배열은 각 위치의 방문 여부와 해당 위치까지 도달하는 데 걸린 이동 횟수를 저장하기 위해 사용된다. 
• 현재위치 N과 숨을 위치 M을 입력받는다. 
• BFS를 사용하여 목표위치까지 도달 여부를 탐색한다.
  (BFS는 한번에 한 레벨씩 모든 경로를 탐색하기 때문에 가장 먼저 M에 도달하는 경로가 최단경로가 된다) 
  • 이동할 수 있는 세 가지 경우(앞 뒤 순간이동)를 탐색하고, 아직 방문하지 않은 위치라면(check배열의 값이 0이라면) check배열을 업데이트한다. 
  • 가장 최초로 값이 업데이트되는 순간이 가장 빠른시간이므로 이동하려는 위치의 값이 0일 때 업데이트한다. 
  • index가 M에 도달하면 탐색을 종료하고, 그때의 이동 횟수를 리턴한다. 
  • index가 M이 되지 않고 모든 탐색을 마쳤다면, M에는 도달할 수 없다는 의미이므로 -1을 리턴한다. 

 

BFS를 사용한 이유 

• BFS(너비우선탐색) 은 한번에 한 레벨씩 탐색하므로, 가장 먼저 도착한 경로가 최단 경로임을 보장한다. 
• 반면, DFS(깊이우선탐색) 은 한 경로를 끝까지 탐색한 후에 다른 경로를 탐색하므로 최단 경로를 찾는 데 적합하지 않다. 

 

 

 

---

https://www.acmicpc.net/problem/1697