[Programmers] 여행경로

본 게시글은 PC 환경에서 보기 편하도록 설정이 되어 있습니다.

여행경로

BFS-DFS 문제로 분류가 되어있는 문제입니다.

저는 DFS로 문제를 풀었습니다.

 

문제의 조건중 눈여겨 봐야할 조건은

 

1. 주어진 항공권은 모두 사용해야 합니다.

2. 만일 가능한 경로가 2개 이상일 경우 알파벳 순서가 앞서는 경로를 return 합니다.

3. 모든 도시를 방문할 수 없는 경우는 주어지지 않습니다.

 

인데, 2번의 조건만 만족시키는 방식으로하면 완전한 탐색이 이루어지지 않는 경우가 발생하여 채점시 1번과 2번을 실패할 수 있습니다.

따라서 이 문제는 2번에 맞춰 정해진 경로들의 우선순위를 완전 탐색해야 함을 빠르게 잡아내는것이 중요한 문제였습니다.

풀이 스타일

Java는 객체지향 언어이기 때문에 알고리즘 문제를 자바로 풀때 객체지향적이게 풀어야 한다고 생각합니다.

따라서 Ticket이라는 객체를 만들고 풀이를 위한 메소드중 Ticket이 해야하는 행동은 Ticket 내부의 메소드로 구현하였습니다.

코드

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.stream.Collectors;

public class TravelPath {

    public static void main(String[] args) {
        String[][] ticketsFirst = {{"ICN", "SFO"}, {"ICN", "ATL"}, {"SFO", "ATL"}, {"ATL", "ICN"}, {"ATL", "SFO"}};
        String[][] ticketsSecond = {{"ICN", "JFK"}, {"HND", "IAD"}, {"JFK", "HND"}};
        Solution solution = new Solution();
        System.out.println(Arrays.toString(solution.solution(ticketsFirst)));
        System.out.println(Arrays.toString(solution.solution(ticketsSecond)));
    }

    static class Solution {
        public String[] solution(String[][] tickets) {
            String[] answer = {};

            List<Ticket> usableTickets = Arrays.stream(tickets)
                    .map(Ticket::new)
                    .collect(Collectors.toList());
            answer = new String[usableTickets.size() + 1];

            List<Ticket> usedTickets = new ArrayList<>();
            Queue<Ticket> canFirstTicket = findFirstTickets(usableTickets);
            while (!canFirstTicket.isEmpty()) {
                Ticket firstTicket = canFirstTicket.poll();
                findPath(firstTicket, usableTickets, usedTickets);
            }

            int index = 0;
            for (Ticket ticket : usedTickets) {
                answer[index] = ticket.getDepart();
                answer[index + 1] = ticket.getDest();
                index++;
            }

            return answer;
        }

        private void findPath(Ticket beforeTicket, List<Ticket> usableTickets, List<Ticket> usedTickets) {
            if (isNotUsable(usableTickets)) {
                return;
            }

            beforeTicket.use();
            usedTickets.add(beforeTicket);

            Queue<Ticket> canNextTickets = findNextTickets(usableTickets, beforeTicket);
            while (!canNextTickets.isEmpty()) {
                Ticket nextTicket = canNextTickets.poll();
                findPath(nextTicket, usableTickets, usedTickets);
            }

            if (isNotUsable(usableTickets)) {
                return;
            }

            beforeTicket.cancel();
            usedTickets.remove(beforeTicket);
        }

        private boolean isNotUsable(List<Ticket> usableTickets) {
            return usableTickets.stream()
                    .noneMatch(Ticket::isUsable);
        }

        private Queue<Ticket> findFirstTickets(List<Ticket> tickets) {
            return tickets.stream()
                    .filter(Ticket::canFirst)
                    .collect(Collectors.toCollection(PriorityQueue::new));
        }

        private Queue<Ticket> findNextTickets(List<Ticket> usableTickets, Ticket beforeTicket) {
            return usableTickets.stream()
                    .filter(Ticket::isUsable)
                    .filter(usableTicket -> usableTicket.getDepart().equals(beforeTicket.getDest()))
                    .collect(Collectors.toCollection(PriorityQueue::new));
        }
    }

    static class Ticket implements Comparable<Ticket> {
        private String depart;
        private String dest;
        private boolean usable = true;

        public Ticket(String[] ticket) {
            this.depart = ticket[0];
            this.dest = ticket[1];
        }

        public String getDepart() {
            return depart;
        }

        public String getDest() {
            return dest;
        }

        public boolean isUsable() {
            return usable;
        }

        public void use() {
            this.usable = false;
        }

        public void cancel() {
            this.usable = true;
        }

        public boolean canFirst() {
            return this.depart.equals("ICN");
        }

        @Override
        public int compareTo(Ticket o) {
            return this.dest.compareTo(o.getDest());
        }
    }
}