13549 - 숨바꼭질 3

이 문제는 두 숫자 N과 K가 주어지고, 이동 방법을 이용해 N을 K로 만드는데 드는 최소 비용(문제에서는 시간)이 얼마인지 구해야 하는 문제이다. 이동 방법에는 두 가지가 있다.

• x+1 또는 x-1로 이동 (비용 1)
• 2*x로 이동 (비용 0)

숫자를 노드로 정의하고 비용을 간선의 가중치로 보면 이 문제가 그래프에서 최소 이동거리를 구하는 문제임을 알 수 있다. 가중치가 모든 간선마다 0 또는 1로 다르기 때문에 다익스트라 알고리즘을 쓰거나 0-1 BFS를 사용하면 이 문제를 풀 수 있다.

🔗 문제 링크

코드

다익스트라

필요한 변수들을 미리 선언한다. INF의 경우 distances 배열을 초기화할 때 무한대를 나타내기 위해 정의한 것으로, 가중치가 0 또는 1이기 때문에 가능한 최대 비용은 100000 일 것이다. 따라서 그것보다 조금 더 큰 100005를 INF로 설정하였다.

costs는 각 간선의 비용을 쉽게 계산할 수 있도록 하기 위해 각 이동 케이스별로 가중치를 담아놓은 것이다.

State 클래스는 우선순위 큐에 넣을 자료형을 정의한 것으로, 현재 상태인 숫자와, 도달하는 데 든 비용(거리)를 저장할 수 있도록 하였다.

class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    static final int INF = 100005;
    static final int[] costs = {1,1,0};
    static class State {
        public int dist;
        public int num;

        public State(int dist, int num) {
            this.dist = dist;
            this.num = num;
        }
    }

그런 다음 시작 위치와 도착해야 할 위치를 입력받는다.

또한 특수 케이스를 미리 처리하여 최적화하였다. 만약 N이 K와 이미 같은 상황이면 당연히 비용이 들지 않을 것이고, N이 K보다 크다면 무조건 1칸씩 뒤로 가야 하기 때문에 (N-K) 만큼의 비용이 들 것이므로 미리 처리하였다.

public static void main(String[] args) throws IOException {
    StringTokenizer st = new StringTokenizer(br.readLine());
    int N = Integer.parseInt(st.nextToken());
    int K = Integer.parseInt(st.nextToken());

    if (N == K) {
        bw.write(0 + "\n");
        bw.flush();
        return;
    }
    else if (N > K) {
        bw.write(N - K + "\n");
        bw.flush();
        return;
    }

다음으로 우선순위 큐와 거리 배열을 선언해 둔다. distances 배열은 N과 K중 가장 큰 것 + 5의 크기로 선언하고, 값을 모두 inf로 채워 둔다. 다음으로 우선순위 큐를 선언해 State.dist 속성을 기준으로 최소 힙의 구조를 가지도록 하였다. 다음으로 시작점의 비용을 0으로 잡고 우선순위 큐에 넣는다.

    int[] distances = new int[Math.max(N, K) + 5];
    Arrays.fill(distances, INF);

    PriorityQueue<State> pq = new PriorityQueue<>(Comparator.comparingLong(e->e.dist));
    distances[N] = 0;
    pq.offer(new State(0, N));

이 부분은 일반적인 다익스트라 알고리즘과 유사하다. 먼저 우선순위 큐에서 원소를 꺼내고, distances 배열의 값과 비교해 유효성을 검사한다. 음수 가중치는 없으므로 s.num == K이면 최소 비용이 확정된 것이므로 루프를 나간다. 다음으로 인접 정점들을 adjs 배열에 담아둔다.

이제 인접 정점별로 간선의 가중치를 구하고, 범위 검사를 한 뒤 adjNum에 대해 새로운 거리를 구해 최소 거리를 확인하고 업데이트한다 (완화). 만약 새로 구한 거리가 최소라면 우선순위 큐에 새 거리와, 이동한 정점을 표시하는 상태를 넣는다.

    while (!pq.isEmpty()) {
        State s = pq.poll();
        if (s.dist > distances[s.num]) continue;
        if (s.num == K) break;
        int[] adjs = {s.num-1, s.num+1, 2*s.num};
        for (int i = 0; i < 3; i++) {
            int adjNum = adjs[i];
            int adjCost = costs[i];
            if (adjNum > Math.max(K, N) + 2 || adjNum < 0) continue;

            int newDist = s.dist + adjCost;
            if (newDist < distances[adjNum]) {
                distances[adjNum] = newDist;
                pq.offer(new State(newDist, adjNum));
            }
        }   
    }

루프를 빠져나오면 K까지 가는 최소 거리를 출력하고 프로그램을 종료한다.

    bw.write(distances[K] + "\n");
    bw.flush();
}

0-1 BFS

전반적인 코드는 유사하니 달라진 부분을 위주로 살펴보자.

차이점 중 하나는 우선순위 큐가 아닌 데크(deque)를 사용한다는 것이다. 이는 간선의 가중치가 0 또는 1뿐이어서 우선순위 큐 없이도 우선순위 큐처럼 deque를 정렬할 수 있다는 점 때문에 가능하다. 또한 deque에 들어가는 자료형은 Integer로 기존처럼 dist까지 함께 넣어두지 않아도 된다.

    int[] distances = new int[Math.max(N, K)+5];
    Arrays.fill(distances, INF);
    Deque<Integer> q = new ArrayDeque<>();
    q.addLast(N);
    distances[N] = 0;

루프도 살펴보자. 먼저 보이는 차이점으로는, deque에서 상태를 꺼낸 뒤에 거리를 통해 유효성 체크를 하지 않음을 알 수 있다. 왜냐하면 0-1 BFS에서는 dist를 상태에 같이 저장하지 않고 전역 배열 distances에 저장하므로 일관성이 깨지지 않기 때문이고, 같은 값이 deque에 2개 이상 있더라도 한 번 먼저 처리된 뒤 후순위의 값은 if (distances[s] + adjCost < distances[adjNum]) 조건을 통해 인접노드가 deque에 추가되지 않기 때문이다.

또한 기존처럼 완화 과정을 통해 거리를 업데이트 하는 과정은 유사하나 adjCost값에 따라 deque에 삽입하는 방식이 다르다. adjCost가 1이라면 deque의 제일 뒤에 넣는다. 만약 adjCost가 0이라면 제일 앞에 넣는다. 이는 우선순위 큐의 동작 방식을 0-1 가중치의 특성과 deque를 통해 따라한 것이라고 볼 수 있다.

    while (!q.isEmpty()) {
        int s = q.pop();
        if (s == K) break;
        int[] adjs = {s+1, s-1, 2*s};
        for (int i = 0; i < 3; i++) {
            int adjNum = adjs[i];
            int adjCost = costs[i];
            if (adjNum > Math.max(K, N) + 2 || adjNum < 0) continue;
            
            if (distances[s] + adjCost < distances[adjNum]) {
                distances[adjNum] = distances[s] + adjCost;
                if (adjCost == 1) 
                    q.addLast(adjNum);
                else
                    q.addFirst(adjNum);
            }
            
        }   
    }

전체 코드

다익스트라

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


class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    static final int INF = 100005;
    static final int[] costs = {1,1,0};
    static class State {
        public int dist;
        public int num;

        public State(int dist, int num) {
            this.dist = dist;
            this.num = num;
        }
    }

    public static void main(String[] args) throws IOException {
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());

        if (N == K) {
            bw.write(0 + "\n");
            bw.flush();
            return;
        }
        else if (N > K) {
            bw.write(N - K + "\n");
            bw.flush();
            return;
        }

        int[] distances = new int[Math.max(N, K) + 5];
        Arrays.fill(distances, INF);

        PriorityQueue<State> pq = new PriorityQueue<>(Comparator.comparingLong(e->e.dist));
        distances[N] = 0;
        pq.offer(new State(0, N));

        while (!pq.isEmpty()) {
            State s = pq.poll();
            if (s.dist > distances[s.num]) continue;
            if (s.num == K) break;
            int[] adjs = {s.num-1, s.num+1, 2*s.num};
            for (int i = 0; i < 3; i++) {
                int adjNum = adjs[i];
                int adjCost = costs[i];
                if (adjNum > Math.max(K, N) + 2 || adjNum < 0) continue;

                int newDist = s.dist + adjCost;
                if (newDist < distances[adjNum]) {
                    distances[adjNum] = newDist;
                    pq.offer(new State(newDist, adjNum));
                }
            }   
        }

        bw.write(distances[K] + "\n");
        bw.flush();
    }
}

0-1 BFS

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


class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    static final int[] costs = {1,1,0};
    static final int INF = 100005;

    public static void main(String[] args) throws IOException {
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());


        if (N == K) {
            bw.write(0 + "\n");
            bw.flush();
            return;
        }
        else if (N > K) {
            bw.write(N - K + "\n");
            bw.flush();
            return;
        }

        int[] distances = new int[Math.max(N, K)+5];
        Arrays.fill(distances, INF);
        Deque<Integer> q = new ArrayDeque<>();
        q.addLast(N);
        distances[N] = 0;

        while (!q.isEmpty()) {
            int s = q.pop();
            if (s == K) break;
            int[] adjs = {s+1, s-1, 2*s};
            for (int i = 0; i < 3; i++) {
                int adjNum = adjs[i];
                int adjCost = costs[i];
                if (adjNum > Math.max(K, N) + 2 || adjNum < 0) continue;
                
                if (distances[s] + adjCost < distances[adjNum]) {
                    distances[adjNum] = distances[s] + adjCost;
                    if (adjCost == 1) 
                        q.addLast(adjNum);
                    else
                        q.addFirst(adjNum);
                }
                
            }   
        }

        bw.write(distances[K] + "\n");
        bw.flush();
    }
}

시간복잡도

다익스트라의 시간복잡도 $O(E \log V)$ 이다. 먼저 정점의 개수부터 생각해보면 간선이 x+1, x-1, 2*x이기 때문에 사실상 거의 N부터 K까지 모든 수를 접근할 수 있어서 노드의 수는 대략 $K-N+1 \le K$ 이다.($K\le N$ 인 경우는 앞서서 처리했다고 본다.) 그리고 간선의 경우도 각 노드별로 대략 3개씩 간선으로 연결되어 있다고 가정하면 간선의 개수는 $3K$개일 것이고 (실제로는 이것보다 많을 것이다), 이를 Big-O 표현법으로 나타내면 $O(K \log K)$일 것이다.

0-1 BFS 시간복잡도 $O(E+V)$이고 위에서 추정한 추정치를 통해 시간복잡도를 대략적으로 구하면 $O(K)$이다

따라서 0-1 BFS가 다익스트라보다 시간복잡도 면에서 더 나은 것을 볼 수 있다.