프로그래머스 여행경로(tickets) 정답 코드

난이도 ★★★★☆

 

문제를 보시려면 여기를 클릭

 

 

 

틀리기 쉬운 입출력 예제

입력	출력
{{"ICN", "JFK"}, {"JFK", "ICN"}, {"ICN", "JFK"}, {"JFK", "ICN"}}	[ICN, JFK, ICN, JFK, ICN]

 

 

 

힌트

전형적인 너비우선탐색(BFS) 문제이지만 구현이 어렵습니다.   1. 위 입출력 예시처럼 동일한 티켓이 여러장 입력될 수도 있다는 점 2. 반드시 모든 티켓을 다 사용해야한다는 점 3. 정렬이 필요한 점   구현하실 때, 이미 방문한 녀석인지 체크할 변수가 필요할텐데 Java는 객체지향 언어잖아요? 별도 배열을 두지마시고 저처럼 객체(Ticket.count)로 만드시길 추천드립니다. 익숙치 않아도 노력해보시길!   ※ String[][] tickets 를 한번 서치하여 ticketSet 을 만들고 싶었는데 count 값을 넣어줄 방법을 못찾아서 tmpCountMap 을 거쳐야만 했습니다. 안거치고 넣을 수 있는 방법이 있을까요?

 

 

 

이하는 코드입니다.

import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Set;
import java.util.TreeSet;
 
public class Solution {
    public String[] solution(String[][] tickets) {
        Map<Ticket, Integer> tmpCountMap = new HashMap<>();    // 표별 개수 세는 용도로 임시
 
        for (String[] ticketStr : tickets) {
            Ticket ticket = new Ticket();
 
            ticket.start = ticketStr[0];
            ticket.end = ticketStr[1];
 
            Integer count = tmpCountMap.get(ticket);
 
            if (count == null) {
                tmpCountMap.put(ticket, 1);
            } else {
                tmpCountMap.put(ticket, count + 1);
            }
        }
 
        Set<Ticket> ticketSet = new TreeSet<>();
 
        for (Ticket ticket : tmpCountMap.keySet()) {
            int count = tmpCountMap.get(ticket);
            ticket.count = count;    // 위에서 tmpCountMap으로 측정한 count
            ticketSet.add(ticket);
        }
 
        String[] answer = new String[tickets.length + 1];
 
        List<String> path = getPath("ICN", ticketSet);
        path.toArray(answer);
 
        return answer;
    }
 
    private LinkedList<String> getPath(String start, Set<Ticket> tickets) {
        LinkedList<String> path = null;
 
        if (allUsed(tickets)) {
            path = new LinkedList<>();
            path.add(start);
            return path;
        }
 
        for (Ticket ticket : tickets) {
            if (ticket.count < 1 || !ticket.start.equals(start)) {
                continue;
            }
 
            ticket.count--;
            path = getPath(ticket.end, tickets);
            ticket.count++;
 
            if (path != null) {
                path.addFirst(start); // This is why use LinkedList
                break;
            }
        }
 
        return path;
    }
 
    private boolean allUsed(Set<Ticket> tickets) {
        for (Ticket ticket : tickets) {
            if (ticket.count > 0) {
                return false;
            }
        }
 
        return true;
    }
 
    private class Ticket implements Comparable<Ticket> {
        String start;
        String end;
        int count;
 
        @Override
        public int compareTo(Ticket that) {
            int startComp = this.start.compareTo(that.start);
 
            if (startComp != 0) {
                return startComp;
            }
 
            return this.end.compareTo(that.end);
        }
 
        @Override
        public boolean equals(Object arg0) {
            if (!(arg0 instanceof Ticket)) {
                return false;
            }
 
            Ticket that = (Ticket) arg0;
 
            return this.start.equals(that.start) && this.end.equals(that.end);
        }
 
        @Override
        public int hashCode() {
            return (start + "," + end).hashCode();
        }
    }
}