[BaekJoon] 1697 숨바꼭질 (java)

🔗 문제 링크

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

📝 문제 풀이 설명

문제는 BFS를 통해 너비 우선 탐색을 하며 각각 $x+1, x-1, x*2$를 큐에 넣으며 탐색을 이어간다.
코드에 작성한 check와 같이 해당 값을 탐색하려면 얼마나 값을 변경해야하는지(깊이)를 저장할 배열을 만들어 관리를 하며 $x+1, x-1, x*2$의 값이 아직 탐색하지 않거나 문제에서 주어진 범위안에 있다면 해당 값은 큐에 넣고 깊이 정보 또한 변경해주면 탐색을 하며 최종 결과를 얻을 수 있을 것이다.

👨🏻‍💻 작성한 코드

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

public class Main {

	public static void main(String[] args) throws Exception {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine()); 
		
		int N = Integer.parseInt(st.nextToken());
		int K = Integer.parseInt(st.nextToken());
		
		if (N==K) System.out.println(0);
		else System.out.println(bfs(N, K));
	}
	
	static int bfs(int n, int k) {
		Queue<Integer> queue = new LinkedList<>();
		
		int[] check = new int[100001];
		queue.add(n);

		int pop;
		while(!queue.isEmpty()) {
			pop = queue.poll();
			if (pop==k) return check[pop];
			
			for (int i: new int[]{pop+1, pop-1, pop*2}) {
				if (0 <= (i) && (i) < check.length && check[i]== 0) {
					check[i] = check[pop]+1;
					queue.add(i);
				}
				
			} 
		}
		return 1;
	}
}

📝 정리

이번 문제는 BFS를 통해 해결을 하는 대표적인 문제이며 이를 응용해 출제되는 문제가 많다고 한다.

나는 BFS코드는 작성할 줄은 알지만 BFS문제를 풀어본 경험이 적어서 그런가 아직까지 문제를 BFS에 적용하는 방법을 바로 알아차리지 못하는 것 같다.

이 또한 문제를 많이 풀면 해결되리라 믿는다...😥