백준 | 13549번. 숨바꼭질 3 - BFS 풀이

⬛ 백준 13549번. 숨바꼭질 3 - BFS 풀이

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

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는 정수이다.

출력

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

---

💚나의 풀이

• 문제 예시에서 N = 5, K= 17 일 경우 2초가 나온다.
• BFS의 레벨 탐색을 생각해서 풀어보면 된다.

풀이 설명

• Node(x, time) 클래스를 생성해서, 순간이동할 경우의 시간과 걷기 이동할 경우의 시간을 분리해서 코드를 짰다.
• 이 문제에서 주의해야 할 점은 N과 K가 모두 1 ~ 100000 사이의 범위에 있다는 점이다.
• 2배 좌표로 가거나 +1 좌표로 갈 때 100,000보다 크지 않도록 제한이 있어야 하고, -1좌표로 갈 때는 0보다 크거나 같은 값인지 제한을 걸어두면서 Queue에 담아야 한다.
• poll한 시점에서 K가 나온다면 가장 작은 cur.time의 값이 최종 답이 될 것이다.

---

🟦 코드

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

public class Main {
	
	static int N,K;
	static int[] visit = 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());
		K=Integer.parseInt(st.nextToken());

		if(N==K) {
			System.out.println(0);
		}else {
			bfs(N);	
		}
		
		br.close();
	}// main()
	
	static void bfs(int num) {
		
		Queue<Integer> qu = new LinkedList<>();
		qu.add(num);
		visit[num]=1;
		
		while(!qu.isEmpty()) {
			int tmp=qu.poll();
			for(int i=0;i<3;i++) {
				int next;
				if(i==0) {
					next=tmp+1;
				}else if(i==1) {
					next=tmp-1;
				}else {
					next=tmp*2;
				}
				
				if(next==K) {
					System.out.println(visit[tmp]);
					return;
				}
				
				if (next >= 0 && next < visit.length && visit[next] == 0) {
                    qu.add(next);
                    visit[next] = visit[tmp] + 1;
                }
			}
		}
	}
	
}