[java]숨바꼭질 4 - 백준13913

문제

• 숨바꼭질 4(백준13913)

풀이

문제 해석을 하자면,

• 1초에 X-1, X+1, 2*X 이동 가능하며 “수빈” 이 “동생” 을 찾는 최소의 시간을 구하는 문제

풀이

• 단순히 위에서 말한 3가지 연산을 “브루트포스” 개념으로 접근하면 충분히 구할 수 있다.
  • 단, 시간초과가 발생할 것이다.
• 이를 위해서 “상태공간트리” 를 그려보면 “BFS” 로 최소 거리 구하는것 처럼 최소시간을 구할 수 있다는걸 알 수 있다.
  • 핵심 원리는 “적절한 범위제한” 과 “이미 기록(방문)한건 무시” 하는게 중요하다.
  • BFS 이기 때문에 “이미 기록(방문)한건 무시” 해도 최소시간(거리)를 구할 수 있다.
  • 이 개념을 잘 이해하고 있어야 이 문제의 풀이가 이해될 것이다.

코드

import java.io.*;
import java.util.*;
/**
 * 1초에 X-1, X+1, 2X 이동 가능
 * => 상태공간트리, BFS특성상 적합
 */
static int N, K; // N:수빈, K:동생
static int[][] dist = new int[100010][2]; // 이전 경로도 같이 기록

public static int calNxt(int cur, int num) {
    if(num == 0) return cur-1;
    else if(num == 1) return cur+1;
    else return cur*2;
}

public static void bfs() {
    for(int i=0;i<100010;i++)
        Arrays.fill(dist[i], -1);
    Queue<Integer> qu = new LinkedList<>();
    qu.add(N);
    dist[N][0] = 0; // "초"(거리) init

    while(!qu.isEmpty()) {
        int cur = qu.peek(); qu.remove();
        for(int i = 0; i<3; i++) {
            int nxt = calNxt(cur, i);
            if(nxt<0||nxt>100005) continue; // 범위 제한(넉넉히 100005까지) => 오버플로 방지
            if(dist[nxt][0] != -1) continue; // 이미 기록된 경우가 "초"(거리)가 작으므로 갱신할 필요가 없다.
            dist[nxt][0] = dist[cur][0]+1; // "초"(거리) 저장
            dist[nxt][1] = cur; // 이전경로 기록
            qu.add(nxt);
        }
    }
}

public static void main(String[] args) throws IOException {
    // input
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer stk = new StringTokenizer(br.readLine(), " ");
    N = Integer.parseInt(stk.nextToken());
    K = Integer.parseInt(stk.nextToken());
    // run
    bfs();
    // output
    StringBuilder sb = new StringBuilder();
    sb.append(dist[K][0]).append('\n');
    Stack<Integer> st = new Stack<>(); // 출력 용도(거꾸로)
    int pre = K; // init
    for(int i = 0 ; i<=dist[K][0]; i++) {
        st.add(pre);
        pre = dist[pre][1]; // pre update
    }
    while(!st.isEmpty()) {
        sb.append(st.peek()).append(' ');
        st.pop();
    }
    System.out.println(sb);
}

느낀점

생략