[백준] 1697번: 숨바꼭질

문제링크 : https://www.acmicpc.net/problem/1697

 

문제풀이

bfs로 풀 수 있는 문제이다.

 

1. X - 1로 이동

2. X + 1로 이동

3. X * 2로 이동

 

세 가지의 경우를 모두 큐에 넣는다.

최대 100,000까지 가능하므로 크기 100,000 + 1인 배열을 생성하여 방문여부를 체크한다.

동생을 찾을 때 까지 (X == K일 때 까지) 작업을 반복한다.

 

소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
import java.util.Queue;
import java.util.LinkedList;

public class p_1697 {
	static final int MAX = 100001;
	static boolean[] visited = new boolean[MAX];
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String input = br.readLine();
		StringTokenizer st = new StringTokenizer(input);
		int N = Integer.parseInt(st.nextToken());
		int K = Integer.parseInt(st.nextToken());

		Queue<Integer> queue = new LinkedList<Integer>();
		queue.offer(N);
		visited[N] = true;
		int second = 0;
		boolean find = false;
		while (true) {
			int size = queue.size();
			for (int i = 0; i < size; i++) {
				int next = queue.poll();
				if (next == K) {
					find = true;
					break;
				}
				
				if (next + 1 < MAX && visited[next + 1] == false) {
					queue.offer(next + 1);
					visited[next + 1] = true;
				}
				
				if (next - 1 >= 0 && visited[next - 1] == false) {
					queue.offer(next - 1);
					visited[next - 1] = true;
				}
				
				if (next * 2 < MAX && visited[next * 2] == false) {
					queue.offer(next * 2);
					visited[next * 2] = true;
				}
			}
			
			if (find) break;
			
			second++;
		}
		
		System.out.println(second);
	}
}