[JAVA] BOJ 백준 12851번 - 숨바꼭질2

목차

• 문제
• 내가 푼 방법
• 자바 코드
• 결과 및 회고

---

1. 문제

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

12851번: 숨바꼭질 2

---

2. 내가 푼 방법

BFS 알고리즘을 이용했고, time 배열에 도착한 최소 시간을 비교하면서 풀어주었다. time 변수의 범위는 time = new int[100001]로 지정했는데, 수빈이와 동생이 갈 수 있는 범위가 0 ~ 100000이기 때문이다.

 

Tuple 클래스를 큐에 넣어주면서 풀었는데,  0 ~ 100000 범위를 벗어날 경우와 tuple.x + 1이 time[dx] 보다 클 경우에는 패스해준다. 또한 dx가 K(수빈이 위치) 일 경우에는 큐에 넣어줄 필요가 없으므로 dx == K일 경우와 나머지인 경우로 구분해 확인해줬다.

public static void solution() {
    method = 1;

    if (N == K) return;

    Queue<Tuple> queue = new LinkedList<>();
    queue.add(new Tuple(N, 0));

    Arrays.fill(time, Integer.MAX_VALUE);

    while (!queue.isEmpty()) {
        Tuple tuple = queue.poll();

        for (int i = 0; i < 3; i++) {
            int dx;

            if (i == 0) dx = tuple.x - 1;
            else if (i == 1) dx = tuple.x + 1;
            else dx = tuple.x * 2;

            if (dx < 0 || dx > 100000 || tuple.t + 1 > time[dx]) continue;

            if (dx == K) {
                if (tuple.t + 1 == time[dx]) {
                    method += 1;
                }
                else if (tuple.t + 1 < time[dx]) {
                    method = 1;
                    time[dx] = tuple.t + 1;
                }
            }
            else {
                time[dx] = tuple.t + 1;
                queue.add(new Tuple(dx, time[dx]));
            }
        }
    }
}

public static class Tuple{
    int x;
    int t;

    public Tuple(int x, int t) {
        this.x = x;
        this.t = t;
    }
}

---

3. 자바 코드

깃허브 풀이 주소

https://github.com/geujeog/BOJ/blob/main/B12851.java

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

class Main {
    static int N;
    static int K;
    static int[] time;
    static int method;

    public static void main (String[] args) throws IOException {
        init();
        solution();
        print();
    }

    public static void solution() {
        method = 1;

        if (N == K) return;

        Queue<Tuple> queue = new LinkedList<>();
        queue.add(new Tuple(N, 0));

        Arrays.fill(time, Integer.MAX_VALUE);

        while (!queue.isEmpty()) {
            Tuple tuple = queue.poll();

            for (int i = 0; i < 3; i++) {
                int dx;

                if (i == 0) dx = tuple.x - 1;
                else if (i == 1) dx = tuple.x + 1;
                else dx = tuple.x * 2;

                if (dx < 0 || dx > 100000 || tuple.t + 1 > time[dx]) continue;

                if (dx == K) {
                    if (tuple.t + 1 == time[dx]) {
                        method += 1;
                    }
                    else if (tuple.t + 1 < time[dx]) {
                        method = 1;
                        time[dx] = tuple.t + 1;
                    }
                }
                else {
                    time[dx] = tuple.t + 1;
                    queue.add(new Tuple(dx, time[dx]));
                }
            }
        }
    }

    public static class Tuple{
        int x;
        int t;

        public Tuple(int x, int t) {
            this.x = x;
            this.t = t;
        }
    }

    public static void print() throws IOException {
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        bw.write(time[K]+"\n");
        bw.write(method+"");

        bw.flush();
        bw.close();
    }

    public static void init() 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());

        time = new int[100001];

        br.close();
    }
}

---

4. 결과 및 회고

처음에 DP인가 싶었는데, 최소 시간(=가장 빠른 시간)을 구하라고 했으므로 BFS임을 알아차렸다.

일차원 BFS, DFS 알고리즘 유형도 머릿속에 박아둬야겠다.