[백준/BFS] 1697: 숨바꼭질 - 자바

문제

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

1697번: 숨바꼭질

 

풀이

BFS를 사용하여 최단 거리를 구하는 문제다.

이전에 BFS를 이용하여 풀어보아서 DFS로 시도하였다.

그러나 DFS로 가지치기를 잘 하지 않는이상 input데이터 범위가 10만이여서 시간초과가 날수밖에없다.

 

DFS로 계속시도하였는데 가지치기를 잘한 DFS풀이를 보고 

그냥 최단거리는 BFS를 사용하는것이 정신건강에 이롭다는 것을 느꼈다.

 

BFS풀이를 할 때에도 q+1, q*2 의 범위를 K까지 지정했는데 답이 계속 틀렸었는데

q값을 2배 증가한 이후에 q-1 을 하여 더 빠르게 탐색하는 경우의 수가 있는 것을 미처 생각하지 못해

의외로 시간을 사용한 문제다.

 

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

public class BOJ_1697 {
	static int N, K;
	static final int MAX_VAL = 1000001;
	static int[] visited = new int[MAX_VAL];
	
	public static void main(String[] args) throws NumberFormatException, 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());
		BFS(N);
		System.out.println(visited[K]);
	}
	
	public static int BFS(int i) {
		Queue<Integer> queue = new LinkedList<>();
		queue.add(i);
		visited[i] = 0;
		
		while(!queue.isEmpty()) {
			int q = queue.remove();
			if(q == K) return visited[q];
		
			if(q-1 >= 0 && visited[q-1] == 0) {
				visited[q-1] = visited[q] + 1;
				queue.offer(q-1);
			}
			if(q+1 <= MAX_VAL && visited[q+1] == 0) {
				visited[q+1] = visited[q] + 1;
				queue.offer(q+1);
			}
			if(q*2 <= MAX_VAL && visited[q*2] == 0) {
				visited[q*2] = visited[q] + 1;
				queue.offer(q*2);
			}
		}
		return 0;
	}
}