알고리즘 풀이 - 백준 13549(숨바꼭질3, 그래프(BFS))

 

관련글

 

그래프 관련 포스팅은 여기를 참조
DFS 관련 포스팅은 여기를 참조
BFS 관련 포스팅은 여기를 참조

 

 

1. 개요

 

문제의 링크는 여기를 참조

 

문제의 내용은 아래의 더보기를 클릭하여 참조

 

 

0부터 100,000 중 수빈이가 걷거나 순간이동으로 매초 -1, 1, x2 만큼 움직일 수 있을 때, 동생의 위치에 도달하는 가장 빠른 시간의 경우의 시간 구하는 문제(x2 이동 시에는 0초 소요)

 

 

2. 풀이

 

이 문제는 이전의 문제(여기)와 비슷한데 x2로 이동 시에는 0초가 소요된다. 따라서, 이전과는 조금 다른 접근이 필요하다.

 

이 문제를 해결할 규칙은 다음과 같다.

① x2 이동을 하게 되는 경우가 0초가 소요되므로 + 방향으로 이동하는 다른 경우 보다는 무조건 우선해서 탐색 해야 한다.
② +1 이동을 하게 되는 경우는 -1 이동 후 x2를 이동하는 경우와 같은데 아래와 같은 예외가 있어 가장 마지막에 점검한다.
  - 예외 케이스 : (현재 위치 : 4, 동생의 위치 : 6인 경우)

예외 케이스는 만약 +1로 2번 이동 시 동생의 위치를 바로 잡을 수 있어 2초가 소요될 것으로 보이지만, -1로 이동 후 x2로 이동하면 1초만에 도달이 가능하다.

 

따라서 위 규칙에 따라 BFS 탐색을 수행하도록 구성하면 문제를 해결할 수 있다.

 

 

3. 코드

 

아래의 코드를 통해 정답을 알아보자.

 

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

public class Main{
    static int[] line = new int[100001];
    static boolean[] visited = new boolean[100001];
    static int n;
    static int k;
    public static void main(String[] args) throws 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());

        // ******************* 그래프 초기화 - n 위치 먼저 큐에 삽입 ****************
        Queue<Integer> q = new LinkedList<>();
        visited[n] = true;
        q.offer(n);

        // ******************** 큐가 비지 않은 동안 탐색 수행 ********************
        int ans = Integer.MAX_VALUE;
        while(!q.isEmpty()){
            int u = q.poll();

            // k위치에 도달했다면 현재 위치 저장
            if(u == k){
                ans = Math.min(ans, line[u]);
                break;
            }

            // -1로 가는 방향을 가장 먼저 체크.
            // +방향으로 가는 것은 - 방향으로 이동 후 x2로 이동하는 경우가 더 빠른데 체크하지 못할 수 있다.
            if(0 <= u-1 && !visited[u-1]){
                q.offer(u-1);
                visited[u-1] = true;
                line[u-1] = line[u]+1;
            }
            
            // x2는 가장 상단 혹은 중간에 두어도 된다.
            // 다만 가장 마지막에 두어서는 안된다. 
            if(u * 2 <= 100000 && !visited[u * 2]){
                q.offer(u*2);
                visited[u*2] = true;
                line[u*2] = line[u];
            }

            // +1 이동은 가장 마지막에 두어야만 한다.
            // 다른 경우의 수가 더 빠를 수 있기 때문이다.
            if(u+1 <= 100000 && !visited[u+1]){
                q.offer(u+1);
                visited[u+1] = true;
                line[u+1] = line[u]+1;
            }
        }
        System.out.println(ans);
        br.close();
    }
}

 

 

읽어주셔서 감사합니다. 오류가 있으면 지적해주시면 반영하겠습니다.