백준 1697 숨바꼭질 (Java)

1. 문제 링크

1697번: 숨바꼭질

 

2. 문제 및 입출력예제

 

3. 문제 풀이

BFS를 이용해 문제를 풀었다.

N과 K가 같을 경우 움직일 필요가 없으니 0을 출력하고 끝난다.

그 외의 경우에는 bfs() 함수로 넘어갔다.

-1, +1, *1를 하면서 각 값이 범위 안에 들어가면 큐에 넣었다.

하나씩 큐에서 빼면서 값이 도착지점에 도착할 때까지 그 과정을 반복하면 된다.

 

4. 코드

import java.util.ArrayDeque;
import java.util.Queue;
import java.util.Scanner;

public class Main {
	private static StringBuilder sb = new StringBuilder();
	static int N, K, cnt;
	
	static class Check{
		int x;
		int num;
		
		public Check(int x, int num) {
			super();
			this.x = x;
			this.num = num;
		}
	}
	
	public static void main(String[] args) throws Exception {
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt();
		K = sc.nextInt();
		cnt = Integer.MAX_VALUE;
		if(N==K) {
			cnt = 0;
		}
		else {
			bfs(N);
		}

		System.out.println(cnt);
	}

	private static void bfs(int start) {
		Queue<Check> queue = new ArrayDeque<>();
		boolean[] visited = new boolean[100001];
		
		queue.offer(new Check(start, 0));
		visited[start] = true;
		
		int current = 0;
		int temp = 0, now=0;
		while(!queue.isEmpty()) {
			Check check = queue.poll();
			current = check.x;
			temp = check.num+1;
			
			for(int i=0; i<3; i++) {
				if(i==0) {
					now = current - 1;
				}
				else if(i==1) {
					now = current +1;
				}
				else if(i==2) {
					now = current * 2;
				}

				if(now >=0 && now <= 100000 && !visited[now]) {
					queue.offer(new Check(now, temp));
					visited[now] = true;
				}
				
				if(now == K) {
					cnt = temp;
					return;
				}
			}
		}
	}
}