[BOJ] 백준 12851 - 숨바꼭질 2 / 13549 - 숨바꼭질 3 / 13913 - 숨바꼭질 4 (Java)

12851 - 숨바꼭질 2

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

문제

수빈이는 동생과 숨바꼭질을 하고 있다. 수빈: 현재 점 N에 있고, 동생은 점 K에 있다.
수빈이의 위치가 x일 때 걷는 경우: 1초 후, x - 1 or x + 1 위치로 이동 / 순간이동 하는 경우: 1초 후 2 * x 위치로 이동

=> 수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지, 
가장 빠른 시간으로 찾는 방법이 몇 가지인지 구하는 프로그램

입력: N (0 <= N <= 100,000), K (0 <= K <= 100,000)
출력
동생을 찾는 가장 빠른 시간
가장 빠른 시간으로 동생을 찾는 방법의 수

---

풀이

• `time[i]`: i번 위치까지 도달하는 데 걸린 최소 시간
• `cnt[i]`: i번 위치에 최소 시간으로 도달하는 방법의 수
• `Arrays.fill(time, -1)`: 방문 X -> -1로 초기화
• 시작 위치 초기화
  • `time[N] = 0`: 시작 지점 N까지 0초
  • `cnt[N] = 1`: 시작 지점 N까지 도달 방법 1가지
• 갈 수 있는 경우 3가지
  • `next < 0 || next >= MAX`: 범위 벗어남 -> 무시
  • 방문 X 경우: `time[next] == -1` => 최초 도달
    • `time[next] = time[cur] + 1`
    • `cnt[next] = cnt[cur]`
  • 방문 O But, 같은 시간에 또 도달: `time[next] == time[cur] + 1`
    • 다른 경로로도 동일한 시간에 도달 O: `cnt[next] += cnt[cur]`

static void bfs() {
    Queue<Integer> q = new LinkedList<>();
    Arrays.fill(time, -1);

    q.offer(N);
    time[N] = 0;
    cnt[N] = 1;

    while (!q.isEmpty()) {
        int cur = q.poll();

        for (int next : new int[]{cur - 1, cur + 1, cur * 2}) {
            if (next < 0 || next >= MAX) continue;

            if (time[next] == -1) {
                time[next] = time[cur] + 1;
                cnt[next] = cnt[cur];
                q.offer(next);
            } else if (time[next] == time[cur] + 1) {
                cnt[next] += cnt[cur];
            }
        }
    }
}

---

예시

수빈: 5, 동생: 17 / 이동 방식: x - 1, x + 1, x * 2

• time[5] = 0, cnt[5] = 1, q = [5]
• 초기 위치(현재 위치): 5 / 가능한 이동: 4, 6, 10
  • 위치: 4 -> time[4] = 1, cnt[4] = 1
  • 위치: 6 -> time[6] = 1, cnt[6] = 1
  • 위치: 10 -> time[10] = 1, cnt[10] = 1
  • => q = [4, 6, 10]
• (1초 후) 현재 위치: 4 / 이동: 3, 5, 8
  • 위치: 3 -> time[3] = 2, cnt[3] = 1 
  • 위치: 5 -> 이미 방문 / 이동: 6, 10
    • 위치: 6 / 이동: 5, 7, 12
      • 위치: 7 -> time[7] = 2, cnt[7] = 1
      • 위치: 12 -> time[12] = 2, cnt[12] = 1
    • 위치: 10 / 이동: 9, 11, 20
      • 위치: 9 -> time[9] = 2, cnt[9] = 1
      • 위치: 11 -> time[11] = 2, cnt[11] = 1
      • 위치: 20 -> time[20] = 2, cnt[20] = 1
  • 위치: 8 -> time[8] = 2, cnt[8] = 1
  • => q = [3, 8, 7, 12, 9, 11, 20]
• (2초 후) 9 -> 18 / 8 -> 16 / 7 -> 14 / 11 -> 22 / 12 -> 24 / 16 -> 17 / 18 -> 17
  • 17에 처음 도달하는 시간은 4초
  • 5 -> 10 -> 9 -> 18 -> 17
  • 5 -> 4 -> 8 -> 16 -> 17

=> 최단 시간: 4초, 방법: 2가지

---

코드

package silver;

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

// 숨바꼭질 2
public class boj_12851 {
    static int N, K;
    static final int MAX = 100_001;
    static int[] time = new int[MAX];
    static int[] count = new int[MAX];

    static void bfs() {
        Queue<Integer> q = new LinkedList<>();
        Arrays.fill(time, -1);

        q.offer(N);
        time[N] = 0;
        count[N] = 1;

        while (!q.isEmpty()) {
            int cur = q.poll();

            for (int next : new int[]{cur - 1, cur + 1, cur * 2}) {
                if (next < 0 || next >= MAX) continue;

                if (time[next] == -1) {
                    time[next] = time[cur] + 1;
                    count[next] = count[cur];
                    q.offer(next);
                } else if (time[next] == time[cur] + 1) {
                    count[next] += count[cur];
                }
            }
        }
    }

    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());

        bfs();
        System.out.println(time[K]);
        System.out.println(count[K]);
    }
}

---

13549 - 숨바꼭질 3

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

문제

수빈이는 동생과 숨바꼭질을 하고 있다. 수빈: 현재 점 N에 있고, 동생은 점 K에 있다.
수빈이의 위치가 x일 때 걷는 경우: 1초 후, x - 1 or x + 1 위치로 이동 / 순간이동 하는 경우: 0초 후 2 * x 위치로 이동

=> 수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램

입력: N (0 <= N <= 100,000), K (0 <= K <= 100,000)
출력: 동생을 찾는 가장 빠른 시간

---

풀이

0-1 VFS(Zero-One BFS)

• 가중치 0 or 1인 그래프에서 최단 시간을 빠르게 찾는 방식
  • x * 2: 0초 
  • x + 1, x - 1: 1초
• `Deque<Integer> dQ = new ArrayDeque<>()`
  • 가중치 0 -> 앞(`offerFirst`)
  • 가중치 1 -> 뒤(`offerLast`)

 

• `time[i]`: i번 위치에 도달하는 최소 시간
  • `time[N] = 0`: 시작 위치 N의 시간은 0초
• `Arrays.fill(time, -1)`: 방문 X -> -1로 초기화
• 이동
  • 순간이동: 가중치 0 -> 시간 증가 X 이동 O => `time[cur * 2] = time[cur]`
    
    • 0초 이동은 우선적으로 처리 -> 큐의 앞에 넣음: `dQ.offerFirst(cur * 2)`
  • 걷기: 가중치 1 -> 이전 시간보다 더 빠르면 갱신
    • 1초 이동은 나중에 처리해도 됨 -> 큐의 뒤에 넣음: `dQ.offerLast(next)`

static void bfs() {
    Deque<Integer> dQ = new ArrayDeque<>();
    Arrays.fill(time, -1);

    dQ.offer(N);
    time[N] = 0;

    while (!dQ.isEmpty()) {
        int cur = dQ.poll();

        if (cur * 2 < MAX && (time[cur * 2] == -1 || time[cur * 2] > time[cur])) {
            time[cur * 2] = time[cur];
            dQ.offerFirst(cur * 2);
        }

        for (int next : new int[]{cur - 1, cur + 1}) {
            if (next < 0 || next >= MAX) continue;
            if (time[next] == -1 || time[next] > time[cur] + 1) {
                time[next] = time[cur] + 1;
                dQ.offerLast(next);
            }
        }
    }
}

---

코드

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

// 숨바꼭질 3
public class boj_13549 {
    static int N, K;
    static final int MAX = 100_001;
    static int[] time = new int[MAX];

    static void bfs() {
        Deque<Integer> dQ = new ArrayDeque<>();
        Arrays.fill(time, -1);

        dQ.offer(N);
        time[N] = 0;

        while (!dQ.isEmpty()) {
            int cur = dQ.poll();

            if (cur * 2 < MAX && (time[cur * 2] == -1 || time[cur * 2] > time[cur])) {
                time[cur * 2] = time[cur];
                dQ.offerFirst(cur * 2);
            }

            for (int next : new int[]{cur - 1, cur + 1}) {
                if (next < 0 || next >= MAX) continue;
                if (time[next] == -1 || time[next] > time[cur] + 1) {
                    time[next] = time[cur] + 1;
                    dQ.offerLast(next);
                }
            }
        }
    }

    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());

        bfs();
        System.out.println(time[K]);
    }
}

---

13913 - 숨바꼭질 4

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

문제

수빈이는 동생과 숨바꼭질을 하고 있다. 수빈: 현재 점 N에 있고, 동생은 점 K에 있다.
수빈이의 위치가 x일 때 걷는 경우: 1초 후, x - 1 or x + 1 위치로 이동 / 순간이동 하는 경우: 1초 후 2 * x 위치로 이동

=> 수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램

입력: N (0 <= N <= 100,000), K (0 <= K <= 100,000)
출력
동생을 찾는 가장 빠른 시간
어떻게 이동해야 하는지 공백으로 구분해 출력

---

풀이

• `time[i]`: i번 위치까지 도달하는 데 걸린 최소 시간
• `prev[i]`: i에 오기 직전에 어디서 왔는지 저장 (경로 복원용)
• `Arrays.fill(time, -1)`: 방문 X -> -1로 초기화
• 시작 위치 초기화
  • `time[N] = 0`: 시작 지점 N까지 0초
  • `prev[N] = -1`: 경로 시작 값 -1
• 갈 수 있는 경우 3가지
  • `next < 0 || next >= MAX`: 범위 벗어남 -> 무시
  • 방문 X 경우: `time[next] == -1` => 최초 도달
    • `time[next] = time[cur] + 1`
    • `prev[next] = cur`: `prev[현재위치] = 이전위치` => next에 오기 직전에 cur에서 옴

=> 경로만 필요하고, 방법의 수 X

BFS는 처음 도달한 게 곧 최단 거리 => K에 처음 도달 시 BFS 끝내도 됨: `if (cur == K) return`

static void bfs() {
    Queue<Integer> q = new LinkedList<>();
    Arrays.fill(time, -1);

    q.offer(N);
    time[N] = 0;
    prev[N] = -1;

    while (!q.isEmpty()) {
        int cur = q.poll();

        if (cur == K) return;

        for (int next : new int[]{cur - 1, cur + 1, cur * 2}) {
            if (next < 0 || next >= MAX) continue;

            if (time[next] == -1) {
                time[next] = time[cur] + 1;
                prev[next] = cur;
                q.offer(next);
            }
        }
    }
}

 

• K부터 prev[]를 따라가며 역추적 -> 경로를 거꾸로 stack에 저장 후 앞에서부터 출력

Stack<Integer> stack = new Stack<>();
for (int i = K; i != -1; i = prev[i]) {
    stack.push(i);
}

while (!stack.isEmpty()) {
    sb.append(stack.pop()).append(" ");
}

---

코드

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

// 숨바꼭질 4
public class boj_13913 {
    static int N, K;
    static final int MAX = 100_001;
    static int[] time = new int[MAX];
    static int[] prev = new int[MAX];

    static void bfs() {
        Queue<Integer> q = new LinkedList<>();
        Arrays.fill(time, -1);

        q.offer(N);
        time[N] = 0;
        prev[N] = -1;

        while (!q.isEmpty()) {
            int cur = q.poll();

            if (cur == K) return;

            for (int next : new int[]{cur - 1, cur + 1, cur * 2}) {
                if (next < 0 || next >= MAX) continue;

                if (time[next] == -1) {
                    time[next] = time[cur] + 1;
                    prev[next] = cur;
                    q.offer(next);
                }
            }
        }
    }

    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());

        bfs();
        sb.append(time[K]).append("\n");

        Stack<Integer> stack = new Stack<>();
        for (int i = K; i != -1; i = prev[i]) {
            stack.push(i);
        }

        while (!stack.isEmpty()) {
            sb.append(stack.pop()).append(" ");
        }

        System.out.println(sb);
    }
}