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

 

관련글

 

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

 

 

1. 개요

 

문제의 링크는 여기를 참조

 

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

 

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

 

 

2. 풀이

 

그래프 탐색(BFS) 방식으로 매우 간단하게 풀 수 있는 문제이다. BFS를 사용하는 이유는 가중치가 1일 때, 최소 비용(시간)의 경우를 보장하는 탐색 방식이기 때문이다.

현재 가중치는 시간이며, 모든 경우에 가중치는 1이 된다.

현재 정점에서 이동 가능한 경우인 +1, -1, x2의 경우를 모두 체크한 뒤 탐색을 시작하여 해당 탐색 위치가 동생의 위치라면 탐색을 중지하면 되는 간단한 문제이다.

 

이 문제는 Dynamic Programming으로도 해결이 가능하다.

코드는 아래의 내용 참조

 

 

3. 코드

 

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

 

① 그래프 탐색 방식(BFS)

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

public class Main{
    static int[] line = new int[100001];
    static boolean[] visited = new boolean[100001];
    static int[] move = {-1, 1, 2};
    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 = 0;
        while(!q.isEmpty()){
            int u = q.poll();
            
            // k위치에 도달했다면 현재 위치 저장
            if(u == k){
                ans = u;
                break;
            }
            
            for(int i=0; i < 3; i++){
                int next = u;
                if(i < 2){
                    // -1, +1 로 이동
                    next += move[i];
                } else {
                    // x2 로 이동
                    next *= move[i];
                }
                
                // 해당 위치가 방문 가능한 경우 큐에 삽입, 방문 처리
                if(0 <= next && next <= 100000 && !visited[next]){
                    visited[next] = true;
                    // 몇 초만에 도달했는지 저장
                    line[next] = line[u] + 1;
                    q.offer(next);
                }
            }
            
        }
        System.out.println(line[ans]);
        br.close();
    }
}

 

② DP 방식

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

public class Main{
    static int[] line = new int[100002];
    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());

        // ***************** 각 위치 이동 시간 *****************
        for(int i=n-1; i >= 0; i--){
        
            // n보다 작은 위치는 -1씩 이동하여 이동만 가능함
            line[i] = line[i+1]+1;
            
            // k 위치가 n보다 작다면 중간에 만날 수 있으니 출력 후 시스템 종료
            if(i == k){
                System.out.println(line[i]);
                System.exit(0);
            }
        }
        
        // ***************** DP로 탐색 수행 ********************
        solve();
        System.out.println(line[k]);
        br.close();
    }

    private static void solve(){
        // k+1에서 -1 이동하는 경우가 빠를 수도 있으니 +1까지 탐색
        for(int i=n+1; i <= k+1; i++){
        
            // 짝수의 경우 아래 2가지 비교
            // 1) [i/2] 위치에서 x2 이동
            // 2) [i-1] 위치에서 +1 이동
            if(i%2 == 0){
                line[i] = Math.min(line[i/2] + 1, line[i-1] + 1);
                
            // 홀수의 경우 아래 2가지 비교
            // 1) [i/2] 위치에서 x2이동 후 +1 이동([i/2] 위치에서 +2 이동)
            // 2) [i-1] 위치에서 +1 이동
            } else {
                line[i] = Math.min(line[i/2] + 2, line[i-1] + 1);
            }
            
            // i 위치의 값이 정해졌다면 i-1 위치도 업데이트 해야 한다.
            // i-1위치는 i위치에서 +1하거나 지금 그 상태일 때를 비교
            line[i-1] = Math.min(line[i] + 1, line[i-1]);
        }
    }
}

 

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