[백준-실버] 숨바꼭질(BOJ 1697)

문제 

문제링크

 

문제 이해하기

• 위치 N에서부터 K 로 이동해야한다.
• 이동 방법은 3가지 방법이 존재한다.
  1. 현재 위치 - 1
  2. 현재 위치 + 1
  3. 현재 위치 * 2
• N에서 K까지 걸리는 최소 시간을 구해야한다.

어떤 알고리즘이 가능한지 검토

1. 완전탐색
   • 모든 경로를 탐색해야해서 너무 많은 시간이 걸린다.
2. 그리디 
   • 현재의 최선 값이 전체 결과의 최선이 되지 않기에 사용하지 못한다.
3. DFS
   • 한 경로를 끝까지 탐색한 뒤 다른 경로를 탐색하기 때문에 최단 시간에 적합하지 않는다.
4. BFS
   • 가중치가 동일한 그래프에서 최단 경로를 찾는데 적합하다.
   • BFS는 레벨 단위로 탐색하므로 가장 먼저 도달한 경로가 최단 경로임을 보장한다.
   • 시간 복잡도는 O(V+E)

 

코드

import java.io.*;
import java.util.*;
public class 숨바꼭질 {
    public static void main(String[] args) throws IOException{
        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());

        Queue<int[]> queue = new LinkedList<>();
        queue.add(new int[]{N, 0});
        boolean[] visited = new boolean[100001];
        visited[N] = true;

        while(!queue.isEmpty()){
            int[] val = queue.poll();
            int position = val[0];
            int count = val[1];

            if(position == K) {
                System.out.println(count);
                break;
            }

            int[] nextPositions = {position - 1, position + 1, position * 2};

            for(int next : nextPositions) {
                if(next >= 0 && next <= 100000 && !visited[next]) {
                    visited[next] = true;
                    queue.add(new int[] {next, count + 1});
                }
            }
        }
    }
}

 

회고

DFS, BFS 개념을 어제 처음 배우고 문제를 풀었기에 이 문제에 어떤 알고리즘을 적용해야 할지 모르겠어서 AI 형님에게 도움을 받았는데, 이번 문제를 통해 가중치가 없는 그래프에서 최단 거리, 최단 시간을 구해야 하는 문제는 BFS를 통해 해결할 수 있다는 것을 배웠다.