[BOJ] 13913. 숨바꼭질 4(BFS, DP).java

#. Problem

https://www.acmicpc.net/problem/13913

* The copyright in this matter is in BOJ

 

#. Resolution Process

  1. Read and understand problem

  2. Redefine the problem + abstract

  3. Create solution plan (select Algorithm, Data structure)

  4. Prove the plan (check performance time and usage memory)

  5. Carry out the plan

  6. Look back on the plan and find a way to improve it

#. Solve

이전 숨바꼭질 문제를 풀었다면 나름 수월하게 해결할 수 있을 것이다.

숨바꼭질

숨바꼭질2

1. 특정 위치에 왔을 때 어느 위치에서 왔는지 기록을 해두자.

예를 들어 path[9]에서 세 가지 방법으로 이동을 할 경우

아래와 같이 기록을 하면 된다. 

(너는 어디서 왔니? 9에서 왔다 느낌으로...?)

path[10] = 9;

path[8] = 9;

path[18] = 9;

2. 수빈이와 동생이 같은 위치일 경우 처리

가장 빠른 시간은 0이다.

하지만! 이동 경로도 출력해 주어야 한다는 것..

계속 틀리길래 다시 보니 이 경우에 이동 경로는 출력을 안 해줬었다는..

3. 수빈이가 동생보다 뒤에 있을 경우

이 부분을 처리해주지 않았을 때,

실행 시간이 4500ms 정도 나와서..... 굉장히 기분이 찝찝했다.

수빈이가 동생보다 뒤에 있으면 X-1 로 계속 이동하는 방법밖에 없는데

불필요하게 다른 방법을 시도해보게 된다. 

예를 들어 100000 0 이 입력될 경우, 

X-1 로만 계속 이동하면 되는데 X+1, X*2 도 시도해보면서 불필요한 시간이 굉장히 소요될 것이다.

#. Code

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97

import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays; import java.util.Collection; import java.util.Collections; import java.util.LinkedList; import java.util.List; import java.util.Queue; import java.util.StringTokenizer;   public class BOJ13913 {       static int N, K, path[];     static int[] dx = { -1, 1, 2 };       public static void main(String[] args) throws IOException {           BufferedReader br = new BufferedReader(new InputStreamReader(System.in));         StringTokenizer st = new StringTokenizer(br.readLine());         StringBuilder sb = new StringBuilder();                  N = Integer.parseInt(st.nextToken()); // 수빈이 위치         K = Integer.parseInt(st.nextToken()); // 동생 위치         path = new int[100001]; // 이동 경로                  // 수빈이와 동생이 같은 위치         if(N == K) {              sb.append(0 + "\n" + N);         }          // 수빈이가 동생보다 뒤에 있을 경우         else if (N > K) {             sb.append(N - K + "\n");             for (int i = N; i >= K; i--) {                 sb.append(i + " ");             }         }          // 수빈이가 동생보다 앞에 있을 경우         else {             sb.append(process() + "\n");                                                  List<Integer> res = new LinkedList<>();             // 동생 위치부터 수빈이 위치까지 되돌아가자.             res.add(K);             while(path[K] != 0) {                 res.add(path[K]);                 K = path[K];             }             // 수빈이의 위치가 0일 경우 예외처리             if(N == 0) res.add(0);                          for (int i = res.size() - 1; i >= 0; i--)                 sb.append(res.get(i) + " ");         }                  System.out.println(sb);     }       private static int process() {           Queue<Subin> q = new LinkedList<>();         int[] dist = new int[100001];                  Arrays.fill(dist, Integer.MAX_VALUE);         q.add(new Subin(N, 0));         dist[N] = 0;                  int nxt = 0;         while(!q.isEmpty()) {             Subin now = q.poll();                          for (int i = 0; i < 3; i++) {                 if(i == 2) nxt = now.x * dx[i];                 else nxt = now.x + dx[i];                                  // 범위를 벗어나거나 멀리 돌아올 경우                 if(nxt < 0 || nxt > 100000 || now.time + 1 >= dist[nxt]) continue;                 path[nxt] = now.x;                 dist[nxt] = dist[now.x] + 1;                 q.add(new Subin(nxt, now.time + 1));             }         }                  return dist[K];     }       static class Subin {         int x, time;           public Subin(int x, int time) {             this.x = x;             this.time = time;         }              } }   Colored by Color Scripter

cs