[BOJ] 12851. 숨바꼭질2(BFS, DP).java

#. Problem

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

* 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

뭔가 쉽게 풀릴 것 같으면서도 안 풀렸던..

몇가지 예외처리가 필요한 문제였다 ㅠuㅠ

1. 수빈이와 동생이 같은 위치에 있을 경우.

시간은 0, 방법의 수는 1이 된다.

2. visit 상태 처리

int visited[100001]

visit 상태는 몇 초 만에 해당 점으로 이동했는지를 저장

** 회고 **

- boolen visited[100001]

처음에는 방문한 점을 다시 방문하지 않았었는데,

이 경우 +1로 이동한 적이 있으면 x2로 이동했을 경우를 확인하지 못하게 된다.

EX) 9 -> 10 로 방문한 적이 있으면 5 -> 10 으로 방문하려고 할 때, 방문하지 않음

- boolean visited[2][100001]

그래서 2차원 visit 상태 배열로 특정 점에 -1, +1, x2 각각으로 이동했을 경우를 체크해주었는데,

이 경우 이동 방법은 다른데 마지막에 같은 방법으로 이동했을 경우를 확인하지 못하게 된다.

EX) 1 (+1) 2 (x2) 4

    1 (x2) 2 (x2) 4 -> 위 방법에서 visit 상태처리가 되었으므로 방문하지 않음

#. 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

import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays; import java.util.LinkedList; import java.util.Queue; import java.util.StringTokenizer;   public class BOJ12851 {       static int N, K, min;     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());           N = Integer.parseInt(st.nextToken()); // 수빈이 위치         K = Integer.parseInt(st.nextToken()); // 동생 위치           if(N == K) System.out.println(0 + "\n" + 1);         else {             min = Integer.MAX_VALUE;             int cnt = process();                          System.out.println(min + "\n" + cnt);         }     }       private static int process() {           int cnt = 0;         Queue<Subin> q = new LinkedList<>();         int[] visited = new int[100001];                  Arrays.fill(visited, Integer.MAX_VALUE);         q.add(new Subin(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 > visited[nxt]) continue;                                  // 동생을 찾았을 경우                 if(nxt == K && now.time + 1 <= min) {                     // 도착 시간과 같은 경우                     if(now.time + 1 == min) cnt++;                     // 도착 시간보다 작을 경우 cnt 초기화                     else {                         min = now.time + 1;                         cnt = 1;                     }                 }                 else {                     q.add(new Subin(nxt, now.time + 1));                     visited[nxt] = now.time + 1;                 }             }         }                  return cnt;     }       static class Subin {         int x, time;           public Subin(int x, int time) {             this.x = x;             this.time = time;         }              } }   Colored by Color Scripter

cs

#. Code_v2

현재 점의 정보는 이전 점의 정보를 이용한다는 점을 활용하면

DP로 해결할 수 있다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class BOJ12851_v2 {
 
    static int N, K;
    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());
 
        N = Integer.parseInt(st.nextToken()); // 수빈이 위치
        K = Integer.parseInt(st.nextToken()); // 동생 위치
 
        if(N == K) System.out.println(0 + "\n" + 1);
        else {
            int[] res = process();
            
            System.out.println(res[0] + "\n" + res[1]);
        }
    }
 
    private static int[] process() {
 
        Queue<Subin> q = new LinkedList<>();
        int[] dist = new int[100001];
        int[] cnt = new int[100001];
        
        Arrays.fill(dist, Integer.MAX_VALUE);
        q.add(new Subin(N, 0));
        dist[N] = 0;
        cnt[N] = 1;
        
        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;
                // 동생을 찾았을 경우
                if(dist[nxt] == now.time + 1) {
                    cnt[nxt] += cnt[now.x];
                } else {
                    dist[nxt] = dist[now.x] + 1;
                    cnt[nxt] += cnt[now.x];
                    q.add(new Subin(nxt, now.time + 1));
                }
            }
        }
        
        int[] res = { dist[K], cnt[K] };
        
        return res;
    }
 
    static class Subin {
        int x, time;
 
        public Subin(int x, int time) {
            this.x = x;
            this.time = time;
        }
        
    }
}
 

line 33) 현재 점까지의 최단 시간을 저장

line 34) 현재 점까지 이동 방법의 수

line 49) 범위를 벗어나거나 현재 점까지 더 많은 시간이 걸렸을 경우는 pass

line 51~52) 동생을 찾았을 경우 이전 점까지 이동 방법의 수를 누적

line 54~56) 동생이 없는 점이라면 

 이전 점까지의 최단 시간 + 1을 저장하고

 이전 점까지 이동 방법의 수를 누적

 큐에 추가!