[JAVA] 백준 알고리즘 1697 : 숨바꼭질 (BFS)

문제

소스

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {

	static int N, K;
	static int visit[] = new int[100001];
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt(); // 수빈
		K = sc.nextInt(); // 동생
		
		bfs();
	}
	
	public static void bfs() {
		Queue<Integer> q = new LinkedList<Integer>();
		
		q.add(N);
		visit[N] = 1;

		while(!q.isEmpty()) {
			N = q.poll();
			
			if (N==K)
				break;
			
			if(N+1 <= 100000 && visit[N+1] == 0) {
				q.add(N+1);
				visit[N+1] = visit[N]+1;
			}
			
			if(N-1 >= 0 && visit[N-1] == 0) {
				q.add(N-1);
				visit[N-1] = visit[N]+1;
			}
			
			if(N*2 <= 100000 && visit[N*2] == 0) {
				q.add(N*2);
				visit[N*2] = visit[N]+1;
			}
		}
		
		System.out.println(visit[K]-1); // 0이 아닌 1에서 시작 해서 -1해주기 
	}
}

출처

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