숨바꼭질3

숨바꼭질 3

 

백준 13549번 문제

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

13549번: 숨바꼭질 3

 

 

1. 문제

 

 

2. 풀이

2.1 풀이 방법

이 문제는 다음 노드로 이동(걷거나 순간이동)할 때의 가중치가 1 또는 0으로 균일하지 않다.

BFS로 풀 수 있는 문제들은 가중치가 균일해서 Queue에 가중치 합이 작은 순으로 순차적으로 들어오게 되어있다.

 

그러나 이 문제는 가중치가 균일하지 않기 때문에 일반적인 BFS 방식으로 문제를 풀게 되면 Queue에 가중치 합이 순차적으로 들어오지 않고, 최소 비용을 구할 수 없다.

 

예를 들어 5에서 출발을 했다고 하면 Queue는 다음과 같이 채워진다.

 

[일반적인 BFS 방식]

위 그림과 같이 비용이 섞여서 Queue에 쌓이게 되므로 최소 비용을 판단할 수 없다.

 

이는 Dequeue를 사용하는 것으로 해결할 수 있다.

 

[Dequeue를 사용한 방식]

 

Dequeue를 사용해서, 가중치가 0인 순간이동으로 이동하는 경우를 Dequeue의 가장 앞에 넣는다.

가중치가 1인 걷기로 이동하는 경우는 Dequeue의 뒤에 넣으면, 위 그림처럼 비용이 오름차순으로 들어가게 된다.

 

이후는 이 과정을 반복해서 목적지에 도착하는 최소 비용을 찾으면 된다.

 

 

2.2 코드

[moveSet, Node]

static int[] moveSet = {-1, 1, 2};

private static class Node {

    int number;
    int time;

    public Node(int number, int time) {
        this.number = number;
        this.time = time;
    }
}

 

moveSet은 다음 노드로 이동할 때 사용되는 배열이다.

Node는 위치정보와 비용(시간)을 갖고 있는 class이다.

 

 

[bfs]

private static Node bfs(Node firstNode, int dist, boolean[] check) {

    Deque<Node> deque = new LinkedList<>();
    deque.offer(firstNode);
    check[firstNode.number] = true;

    while (!deque.isEmpty()) {

        Node currentNode = deque.poll();
        check[currentNode.number] = true;

        if (currentNode.number == dist) {
            return currentNode;
        }

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

            int nextNumber;
            if (i == 2) {
                nextNumber = currentNode.number * moveSet[i];
            } else {
                nextNumber = currentNode.number + moveSet[i];
            }

            if (nextNumber < 0 || nextNumber > 100000 || check[nextNumber]) {
                continue;
            }

            //순간이동이면 앞에, 걷기이면 뒤에 넣어준다.
            if (i == 2) {
                deque.push(new Node(nextNumber, currentNode.time));
            } else {
                deque.offer(new Node(nextNumber, currentNode.time + 1));
            }
        }
    }

    return null;
}

 

일반적인 BFS이지만 Queue에 다음 Node를 넣어줄 때, 순간이동이 사용됐다면 앞에, 걷기가 사용되었다면 뒤에 넣어준다.

 

 

[main]

public static void main(String[] args) throws IOException {

    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer st = new StringTokenizer(br.readLine(), " ");
    int n = Integer.parseInt(st.nextToken());
    int k = Integer.parseInt(st.nextToken());

    boolean[] check = new boolean[100001];
    Node node = new Node(n, 0);

    Node result = bfs(node, k, check);

    System.out.println(result.time);
}

 

 

 

3. 전체 코드

[전체 코드]

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Deque;
import java.util.LinkedList;
import java.util.StringTokenizer;

public class Main {

    static int[] moveSet = {-1, 1, 2};

    private static class Node {

        int number;
        int time;

        public Node(int number, int time) {
            this.number = number;
            this.time = time;
        }
    }

    private static Node bfs(Node firstNode, int dist, boolean[] check) {

        Deque<Node> deque = new LinkedList<>();
        deque.offer(firstNode);
        check[firstNode.number] = true;

        while (!deque.isEmpty()) {

            Node currentNode = deque.poll();
            check[currentNode.number] = true;

            if (currentNode.number == dist) {
                return currentNode;
            }

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

                int nextNumber;
                if (i == 2) {
                    nextNumber = currentNode.number * moveSet[i];
                } else {
                    nextNumber = currentNode.number + moveSet[i];
                }

                if (nextNumber < 0 || nextNumber > 100000 || check[nextNumber]) {
                    continue;
                }

                if (i == 2) {
                    deque.push(new Node(nextNumber, currentNode.time));
                } else {
                    deque.offer(new Node(nextNumber, currentNode.time + 1));
                }
            }
        }

        return null;
    }


    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        int n = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());

        boolean[] check = new boolean[100001];
        Node node = new Node(n, 0);

        Node result = bfs(node, k, check);

        System.out.println(result.time);
    }
}