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

 

관련글

 

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

 

 

1. 개요

 

문제의 링크는 여기를 참조

 

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

 

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

그리고 출력 시, 가장 빠르게 이동하는 경우의 이동 경로 또한 출력해야 하는 문제

 

 

2. 풀이

 

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

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

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

 

다만, 이동 경로 또한 표시를 해주어야 하는데, 이 부분은 BFS 탐색으로 이동 시, 이전의 정점을 표기하도록 하여 동생의 위치에서 부터 이전의 정점을 지속적으로 찾아 더 이상 찾을 수 없을 때까지 그 이동 경로를 저장하는 방식으로 해결하였다.

Stack을 이용해서 그 경로를 저장하고 다시 뽑아서 출력하면 최초 위치부터 이동 경로를 찾아낼 수 있다.

 

 

3. 코드

 

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

 

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

public class Main{
    static int[] line = new int[100001];
    static boolean[] visited = new boolean[100001];
    static int[] parent = new int[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;
        parent[n] = -1;
        q.offer(n);
        
        
        // ******************** 큐가 비지 않은 동안 탐색 수행 ********************
        int c = 0;
        while(!q.isEmpty()){
            int u = q.poll();
            
            // k위치에 도달했다면 현재 위치 저장
            if(u == k){
                c = 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;
                    
                    // 다음 탐색 정점의 이전 정점을 현재 정점으로 저장
                    parent[next] = u;
                    q.offer(next);
                }
            }
        }
        
        // 현재 이동한 시간 출력
        System.out.println(line[c]);
        
        // 현재 이동한 순서를 stack에 넣는다.
        Stack<Integer> stack = new Stack<>();
        while(parent[c] != -1){
            stack.add(c);
            c = parent[c];
        }
        
        // 이동 순서대로 출력 수행
        StringBuilder sb = new StringBuilder();
        sb.append(c).append(" ");
        
        while(!stack.isEmpty()){
            sb.append(stack.pop()).append(" ");
        }
        System.out.println(sb);
        br.close();
    }
}

 

 

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