백준 1697번 java 풀이 - bfs

 

풀이

이 문제는 bfs 알고리즘을 적용하여 풀면 쉽게 풀 수 있습니다.

큐와 배열을 이용하여 수빈이의 위치를 큐에 넣고 큐에서 값을 뽑을 때마다 갈 수 있는 위치(x-1, x+1,x*2)를 큐에 넣어주며 bfs함수를 다시 호출하는 방식으로 해결할 수 있습니다.

물론 시간을 줄이기 위해 boolean 배열을 사용하여 방문한 곳을 체크하는 조건을 추가할 수도 있습니다.

또한 이동 횟수(=시간)을 구해야 하기 때문에 배열을 하나 더 만들어 해당 인덱스까지 갈 때 소요되는 값을 저장해야 합니다.

 

코드

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

class Main{
	static int[] array;
	static boolean[] bool;
	static int bro = 0;
	static Queue<Integer> queue = new LinkedList<>();
	public static void main(String[] args) throws java.lang.Exception{
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int subin = Integer.parseInt(st.nextToken());
		bro = Integer.parseInt(st.nextToken());
		
		if(subin >= bro){
			array = new int[subin+1];
			bool = new boolean[subin+1];
		}else{
			array = new int[bro*2];
			bool = new boolean[bro*2];
		}
		queue.add(subin);
		bool[subin] = true;
		bfs(subin);
	}
	
	public static void bfs(int x){
		int num = queue.poll();
		int size = array.length;
		if(num == bro){
			System.out.println(array[num]);
			return;
		}
		
		if(x > 0 && bool[x-1] == false){
			queue.add(x-1);
			array[x-1] = array[x] + 1;
			bool[x-1] = true;
		}
		
		if(x < size - 1 && bool[x+1] == false){
			queue.add(x+1);
			array[x+1] = array[x] + 1;
			bool[x+1] = true;
		}
		
		if(x*2 < size && bool[x*2] == false){
			queue.add(x*2);
			array[x*2] = array[x] + 1;
			bool[x*2] = true;
		}
		
		bfs(queue.peek());
	}
}