[programmers/java] 카운트 다운 - Dijkstra, PriorityQueue

1. 문제 개요

- url : https://school.programmers.co.kr/learn/courses/30/lessons/131129#

 

"카운트다운"은 주어진 점수 target을 최소한의 다트 수로 정확히 0점으로 만드는 다트 게임이다. 각 다트는 다음과 같은 점수를 획득할 수 있다.

• 불(BULL): 50점
• 싱글(SINGLE): 1~20점
• 더블(DOUBLE): 2~40점 (2배)
• 트리플(TRIPLE): 3~60점 (3배)

조건은 다음과 같다.

1. 가능한 한 최소한의 다트 수로 0점을 만드는 것이 우선이다.
2. 동률일 경우 싱글 또는 불을 더 많이 던진 방법이 우선이다.

---

2. 해결 전략

본 문제는 상태 전이 기반 최적화 문제이며, 우선순위 큐를 이용해 가장 우선순위가 높은 상태부터 탐색하는 방식으로 풀이할 수 있다. 이를 위해 remain (남은 점수), round (던진 다트 수), single (싱글/불 던진 수)를 상태로 구성하여 최소 비용 탐색을 수행한다.

우선순위 큐에는 다음 우선순위가 적용된다.

1. 던진 다트 수가 적을수록 우선
2. 다트 수가 같을 경우 싱글 또는 불을 더 많이 던진 경우 우선

---

3. 전체 소스 코드

import java.util.*;

class Solution {
    public int[] solution(int target) {
        PriorityQueue<Item> pq = new PriorityQueue<>();
        Set<Integer> visited = new HashSet<>();

        pq.offer(new Item(target, 0, 0));

        while (!pq.isEmpty()) {
            Item cur = pq.poll();

            if (cur.remain == 0) {
                return new int[]{cur.round, cur.single};
            }

            if (visited.contains(cur.remain)) continue;
            visited.add(cur.remain);

            // 불(BULL, 50점)
            if (cur.remain >= 50) {
                pq.offer(new Item(cur.remain - 50, cur.round + 1, cur.single + 1));
            }

            // 1~20점에 대해 싱글, 더블, 트리플
            for (int i = 1; i <= 20; i++) {
                if (cur.remain >= i) {
                    pq.offer(new Item(cur.remain - i, cur.round + 1, cur.single + 1)); // 싱글
                }
                if (cur.remain >= i * 2) {
                    pq.offer(new Item(cur.remain - i * 2, cur.round + 1, cur.single)); // 더블
                }
                if (cur.remain >= i * 3) {
                    pq.offer(new Item(cur.remain - i * 3, cur.round + 1, cur.single)); // 트리플
                }
            }
        }

        return new int[]{}; // 도달 불가한 경우 (존재하지 않음)
    }

    class Item implements Comparable<Item> {
        int remain;
        int round;
        int single;

        public Item(int remain, int round, int single) {
            this.remain = remain;
            this.round = round;
            this.single = single;
        }

        @Override
        public int compareTo(Item o) {
            if (this.round != o.round) return this.round - o.round;
            return o.single - this.single; // 싱글/불 더 많이 던진 경우 우선
        }
    }
}

---

4. 핵심 구현 설명

4.1 우선순위 큐

• PriorityQueue<Item>을 사용하여 가장 유리한 상태부터 처리한다.
• 내부적으로 compareTo 기준에 따라 정렬된다.

관련 메서드 설명

함수	설명
pq.offer(element)	요소를 큐에 삽입하고 내부 우선순위에 따라 정렬한다.
pq.poll()	우선순위가 가장 높은 요소를 제거하고 반환한다.
pq.isEmpty()	큐가 비어있는지를 판단한다.

4.2 상태 클래스: Item

@Override
public int compareTo(Item o) {
    if (this.round != o.round) return this.round - o.round;
    return o.single - this.single;
}

반환값	의미
음수 (< 0)	this 객체가 o 객체보다 앞에(우선) 와야 함
0	this 객체와 o 객체는 동등한 우선순위를 가짐
양수 (> 0)	this 객체가 o 객체보다 뒤에(후순위) 와야 함