• 카테고리

    질문 & 답변
  • 세부 분야

    알고리즘 · 자료구조

  • 해결 여부

    미해결

우선순위 큐를 활용해도 되나요?

23.04.17 22:07 작성 23.04.17 22:08 수정 조회수 343

0

우선순위 큐를 써서 문제를 풀었는데 채점 지원이 안되다 보니 제 논리에 허점이 있나 확인차 질문드립니다.

도착지 정보와 현재 지점까지 오는데 걸리는 비용, 환승 횟수 정보를 가지고 있는 Path 클래스를 이용했습니다.

static class Path implements Comparable<Path>{
    int end, cost, t;

    public Path(int end, int cost, int t) {
        this.end = end;
        this.cost = cost;
        this.t = t;
    }

    @Override
    public int compareTo(Path p) {
        return this.cost - p.cost;
    }
}

public int solution(int n, int[][] flights, int s, int e, int k){
    int answer = 0;

    ArrayList<ArrayList<Path>> list = new ArrayList<>();
    for(int i = 0; i < n; i++) {
        list.add(new ArrayList<>());
    }

    for (int[] flight : flights) {
        int start = flight[0];
        int end = flight[1];
        int cost = flight[2];
        list.get(start).add(new Path(end, cost, 0));
    }

    PriorityQueue<Path> pq = new PriorityQueue<>();
    for (Path path : list.get(s)) {
        pq.add(path);
    }

    while(!pq.isEmpty()) {
        Path cur = pq.poll();
        if(cur.t <= k && cur.end == e) {
            answer = cur.cost;
            break;
        }
        for (Path path : list.get(cur.end)) {
            pq.add(new Path(path.end, path.cost + cur.cost, cur.t + 1));
        }
    }

    return answer == 0 ? -1 : answer;
}

 클래스를 만들지 않고 List<int[]> 로 만드시는 이유도 궁금합니다. 배열로 만들면 int[0]이 무엇이 의미하는지 알기 힘들지만, 클래스로 만들면 end, cost 등 변수 이름으로 표현하기더 쉬워서 좋은 것 같은데 알고리즘에는 부적합한가요?

답변 1

답변을 작성해보세요.

1

안녕하세요^^

  1. 잘 하신 코드입니다. 다만 무한루프에 빠질 수 있는 코드입니다. 아래 입력의 경우 무한루프에 빠지게 되는 입력입니다.

System.out.println(T.solution(4, new int[][]{{0, 3, 12},{2, 0, 15}, {3, 1, 16}, {1, 3, 16}}, 3, 0, 3));

 

  1. 코테를 실제 시험보다 보면 시간이 부족할 때가 많습니다. 그래서 그냥 클래스를 안 만들고 바로 배열로 저는 합니다. 별다른 이유는 없습니다.