[BOJ] 13549:숨바꼭질 3

0. 문제

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

13549번: 숨바꼭질 3

1. 문제분석

-  현재 위치에서 다른 위치로 이동하는 경우의 수가 여러가지이고, 이 때에 최단거리를 구하라는 점에서 BFS 알고리즘을 활용해야 함을 알 수 있다. 하지만 본 문제는 일반적인 BFS 문제와는 다르게 다른 위치로 이동하는 비용이 각자 다르고 그 비용이 모두 0 또는 1 이라는 점에서 기존의 BFS 알고리즘에서 더 나아간 0-1 BFS 알고리즘을 사용해야 한다.

 

2. 주의할 점

2-1. 0-1 BFS 알고리즘

- queue를 사용하는 기존의 BFS와 달리, deque을 사용한다. (Java에서는 LinkedList를 queue로도, deque로도 쓸 수 있다.)

- 간선의 비용(문제에서는 걸리는 시간)이 0인 경우(순간이동, x*2)에는, 구하고자 하는 최소비용이 그대로 유지되어야 하므로, bfs 알고리즘 상 queue의 맨 앞에 와야(LinkedList.add()) 한다. 간선의 비용이 1인 경우(x+-1)에는 구하고자 하는 최소비용이 증가(+1)하므로 queue의 맨 뒤에(LinkedList.push()) 와야한다.

 

- 방문하는 노드에 대한 visited를 사용해 한번 진입한 위치(노드)는 다시 방문하지 않아야 한다. 그렇지 않으면 비용이 0인 경우(x*2)의 노드로 진행할 때 메모리 오버플로우가 발생할 것이다.

 

3. 소스코드(Java)

// boj 13549 숨바꼭질 3
// 0-1 bfs

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

public class boj_13549 {

    static int N, K;
    static final int MAX = 100000 * 2;
    static LinkedList<Pair> q = new LinkedList<>();
    static boolean[] visited = new boolean[MAX + 1];

    static class Pair {
        int loc;
        int sec;
        Pair (int l, int s) {
            this.loc = l;
            this.sec = s;
        }
    }

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = stoi(st.nextToken());
        K = stoi(st.nextToken());
        q.add(new Pair(N, 0));
        while (!q.isEmpty()) {
            Pair now = q.pop();
            if (visited[now.loc]) continue;
            if (now.loc == K) {
                System.out.print(now.sec);
                return;
            }
            visited[now.loc] = true;
            if (now.loc * 2 <= MAX) q.push(new Pair(now.loc * 2, now.sec));
            if (now.loc - 1 >= 0) q.add(new Pair(now.loc - 1, now.sec + 1));
            if (now.loc + 1 <= MAX) q.add(new Pair(now.loc + 1, now.sec + 1));
        }
    }

    static int stoi(String s) { return Integer.parseInt(s);};
}

4. 여담

- bfs 문제에도 여러 변형이 있구나를 느꼈다.

- visited로 인해서 다른 문제를 잘못 꼬아 생각하기도 하지만, 이렇게 visited가 꼭 필요한 문제도 있다는것!