[백준] G5 13549번 숨바꼭질 3 (JAVA)

문제 출처 - Baekjoon Online Judge

문제는 여기

13549번: 숨바꼭질 3

[문제] 

수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 0초 후에 2*X의 위치로 이동하게 된다.

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

[입력]

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

[출력]

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

 

---

[풀이]

1. 입력을 받아 값들을 대입해준다.

2. 시간과 위치를 담을 수 있는 클래스를 만들어준다.

3. 2. 에서 만든 클래스를 사용하여 bfs 탐색을 진행한다.

4. 현재 위치가 주어진 위치와 동일하다면 시간의 최솟값을 갱신해준다.

5. 위치를 현재 위치 * 2로 이동을 할 경우는 시간의 증가가 없으므로 그냥 bfs 탐색을 해주고 아닌 경우는 시간 + 1을 하여 bfs 탐색을 진행해준다.

6. 모든 탐색이 끝나면 결과를 출력한다.

[접근]

1. 일반적인 bfs 문제라고 생각하였는데 클래스를 만들어 이를 통해 bfs 탐색을 해주면 되는 문제였다.

[코드]

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

public class Main {
	static int min = Integer.MAX_VALUE;
    static int n, k;
    static int max = 100000;
    static boolean[] visited = new boolean[max + 1];
    
    public static void main(String args[]) throws Exception {
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer st = new StringTokenizer(br.readLine());
        
    	// 입력받기
        n = Integer.parseInt(st.nextToken());
        k = Integer.parseInt(st.nextToken());
        
        // bfs 탐색
        bfs();
        
        System.out.println(min);
    }
    
    public static void bfs() {
        Queue<Subin> q = new LinkedList<>();
        
        q.offer(new Subin(n, 0));
        
        while(!q.isEmpty()) {
            Subin subin = q.poll();
            visited[subin.loc] = true;
            
            // 목표지점에 도착했을 경우
            if (subin.loc == k)
            	// 가장 적은 시간을 찾기 위해 Math.min을 사용해서 최단시간을 탐색
            	min = Math.min(min, subin.time);
            
            // 순간이동을 하였을 때 최대 거리를 넘어가지 않고, 해당 위치를 방문한적이 없다면
            if (subin.loc * 2 <= max && visited[subin.loc * 2] == false)
            	// 순간이동은 시간의 증가가 없음
            	q.offer(new Subin(subin.loc * 2, subin.time));
            
            // X+1로 이동하였을 때 최대 거리를 넘어가지 않고, 해당 위치를 방문한적이 없다면
            if (subin.loc + 1 <= max && visited[subin.loc + 1] == false)
            	// 1초 증가
            	q.offer(new Subin(subin.loc + 1, subin.time + 1));
            
            // X-1로 이동하였을 때 최대 거리를 넘어가지 않고, 해당 위치를 방문한적이 없다면
            if (subin.loc - 1 >= 0 && visited[subin.loc - 1] == false)
            	// 1초 증가
            	q.offer(new Subin(subin.loc - 1, subin.time + 1));
        }
    }
    
    public static class Subin {
        int loc; // 위치
        int time; // 시간
        
        public Subin(int loc, int time) {
            this.loc = loc;
            this.time = time;
        }
    }

}