1697_숨바꼭질 (JAVA)

1697번: 숨바꼭질

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

public class Main {
	static int N;
	static int K;
	static int[] visited = new int[100001];

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt();
		K = sc.nextInt();

		if(N>=K)
			System.out.println(N-K);
		else
			BFS(N);
	}

	public static void BFS(int N){
		Queue<Integer> q = new LinkedList<Integer>();
		q.offer(N);
		visited[N] = 1;
		
		while(!q.isEmpty()){
			int cur = q.poll();
			for(int i=0; i<3; i++){
				int next;
				if(i==0)
					next = cur-1;
				else if(i==1)
					next = cur+1;
				else
					next = cur*2;

				if(next == K){
					System.out.println(visited[cur]);
					return;
				}
				if(next>=0 && next<=100000) {
					if (visited[next] == 0) {
						q.offer(next);
						visited[next] = visited[cur]+1;
					}
				}
			}
		}
	}
}

 

 

[문제 풀이 생각 과정]

 

1. 이동할 수 있는 경우는 -1, +1, *2 이렇게 세 가지 경우이다.

 

2. for문을 이용해 세 가지 경우를 next로 설정한다.

 

3. next==K가 되기까지 다음의 과정을 거친다.

   1) 0 <= next <= 100000 (문제에서 주어진 N,K의 범위)에 next가 해당하고,

      숫자next에 방문했는지 확인한다.

 

   2) 만약 방문안했다면 = visited[next]==0이라면

      큐에 넣고 visited[next]값을 수정한다.

 

   3) visited[next] = visited[cur]+1의 의미는!

      cur -> next로 이동할때 방문안했고 next범위 안에 있다는 조건에 해당하면 +1 해준다.