알고리즘 / Java / 프로그래머스 - 여행경로

프로그래머스 -  여행경로

코딩테스트 연습 - 여행경로

문제 해설

이번 문제는 조금 까다로운 조건이 하나 있습니다.

• 경로는 2개 이상일 수 있다.
• 2개 이상인 경우 알파벳 순서가 앞서는 경로를 return 한다.

그래서 전략은 다음과 같습니다.

1. 경로정보를 가지고 있는 객체를 사용할 것이다.

2. 가능한 경우의 객체를 우선순위큐에 넣고 정의해준 compareTo 메서드에 따라 알파벳 순서가 앞서는 경로를 return 한다.

 

정답 코드

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Queue;

public class Solution {
    class Path implements Comparable<Path> {
        private int count;
        //거쳐온 공항들
        private List<String> airports;
        //방문 했는지 확인
        private boolean[] isVisits;

        public Path(int count, List<String> airports, boolean[] isVisits) {
            this.count = count;
            this.airports = airports;
            this.isVisits = isVisits;
        }

        public String getCurrentLocation() {
            return this.airports.get(this.airports.size() - 1);
        }

        //우선순위 큐에서 비교의 기준이 될 메서드
        @Override
        public int compareTo(Path o) {
            for (int i = 0; i < airports.size(); i++) {
                if (this.airports.get(i).equals(o.airports.get(i))) {
                    continue;
                }
                return this.airports.get(i).compareTo(o.airports.get(i));
            }
            return 0;
        }
    }

    public String[] solution(String[][] tickets) {
        //너비우선탐색을 위한 큐 생성
        Queue<Path> pathQue = new LinkedList<>();
        ArrayList<String> list = new ArrayList<>(Arrays.asList("ICN"));
        pathQue.offer(new Path(0, list, new boolean[tickets.length]));

        //가능한 경로들을 담을 우선순위큐 생성
        PriorityQueue<Path> answerPQue = new PriorityQueue<>();

        while (!pathQue.isEmpty()) {
            Path path = pathQue.poll();
            if (path.count == tickets.length) {
                answerPQue.offer(path);
                continue;
            }
            for (int i = 0; i < tickets.length; i++) {
                if (tickets[i][0].equals(path.getCurrentLocation()) && !path.isVisits[i]) {
                    List<String> airports = new ArrayList<>(path.airports);
                    boolean[] isVisits = path.isVisits.clone();
                    airports.add(tickets[i][1]);
                    isVisits[i] = true;
                    pathQue.offer(new Path(path.count + 1, airports, isVisits));
                }
            }
        }

        return answerPQue.poll().airports.toArray(new String[0]);
    }
}