[Lv3] 여행경로

https://programmers.co.kr/learn/challenges

프로그래밍 강의 | 프로그래머스

문제 설명

 

주어진 항공권을 모두 이용하여 여행경로를 짜려고 합니다. 항상 ICN 공항에서 출발합니다.

항공권 정보가 담긴 2차원 배열 tickets가 매개변수로 주어질 때, 방문하는 공항 경로를 배열에 담아 return 하도록 solution 함수를 작성해주세요.

 

제한사항

• 모든 공항은 알파벳 대문자 3글자로 이루어집니다.
• 주어진 공항 수는 3개 이상 10,000개 이하입니다.
• tickets의 각 행 [a, b]는 a 공항에서 b 공항으로 가는 항공권이 있다는 의미입니다.
• 주어진 항공권은 모두 사용해야 합니다.
• 만일 가능한 경로가 2개 이상일 경우 알파벳 순서가 앞서는 경로를 return 합니다.
• 모든 도시를 방문할 수 없는 경우는 주어지지 않습니다.

입출력 예

tickets	return
[["ICN", "JFK"], ["HND", "IAD"], ["JFK", "HND"]]	["ICN", "JFK", "HND", "IAD"]
[["ICN", "SFO"], ["ICN", "ATL"], ["SFO", "ATL"], ["ATL", "ICN"], ["ATL","SFO"]]	["ICN", "ATL", "ICN", "SFO", "ATL", "SFO"]

 

입출력 예 설명

예제 #1

[ICN, JFK, HND, IAD] 순으로 방문할 수 있습니다.

예제 #2

[ICN, SFO, ATL, ICN, ATL, SFO] 순으로 방문할 수도 있지만 [ICN, ATL, ICN, SFO, ATL, SFO] 가 알파벳 순으로 앞섭니다.

 

 

---

 

모든 도시가 방문 가능한 예제가 주어집니다.

 

가능한 경로가 2개 이상일 경우 알파벳 순서가 앞서는 경로로 갑니다. → 정렬을 사용합니다.

 

모든 티켓을 소진해야합니다.(남는 티켓이 있으면 안됩니다.) → DFS/BFS로 풀이합니다.

 

 

String[][] tickets = {{"ICN", "BBB"}, {"ICN", "AAA"}, {"BBB", "ICN"}, {"AAA", "SSS"}, {"SSS", "DDD"}, {"SSS", "CCC"}, {"DDD", "SSS"}, {"CCC", "SSS"}};

의 경우를 생각해봅시다.

 

"ICN"에서 "BBB"로 갈 수도 있고, "AAA"로 갈 수도 있습니다.

 

정렬 조건만 생각한다면 "AAA"로 가면 될 것 같지만,

 

"ICN"-"AAA"-"SSS"-"CCC"-"SSS"-DDD"-"SSS"에서 더 이상 갈 곳을 잃은 채 ["ICN","BBB"], ["BBB","ICN"] 티켓이 남게 됩니다.

 

"BBB"로도 가는 경우를 생각하면, "ICN"-"BBB"-"ICN"-"AAA"-"SSS"-"CCC"-"SSS"-DDD"-"SSS"으로 모든 티켓 소진이 가능합니다.

 

이래서 두 가지 조건을 모두 생각해야 합니다.

 

풀이는 두가지가 있습니다.

 

1. 갈 수 있는 모든 경로로 탐색을 마쳐서 전 티켓 소모경로들을 만든 다음에(DFS),

그 중 알파벳 순이 빠른 순이 애를 마지막으로 정렬을 이용해 빼와야합니다(정렬).

String[] answer들을 여러 개 만들어서, 저장소에 넣어둔 후, 정렬을 이용해 빼오는 것.

 

2. 미리 tickets를 알파벳 순으로 정렬해서(선정렬),

탐색 자체를 정렬과 같은 순으로 했을 때 처음으로 만들어지는 전 티켓 소모경로가 정답.

 

우리는 2로 갑니다. 단 하나의 경우만 얻으면 되므로.

 

 

static String[] fanswer;

public String[] solution(String[][] tickets) {
    Comparator<String[]> c1 = (a,b)->{
        if(a[0].compareTo(b[0])!=0) return (a[0].compareTo(b[0]));
        else return (a[1].compareTo(b[1]));
    };
    Arrays.sort(tickets, c1);
    boolean[] check = new boolean[tickets.length];
    String[] answer = new String[tickets.length+1];
    answer[0] = "ICN";
    fanswer = null;
    set(tickets, check, 0, "ICN", answer);
    return fanswer;
}

tickets를 정렬합니다.

출발지가 다르면 출발지를 오름차순으로(1순위),

출발지가 같으면 도착지를 오름차순으로(2순위) 합니다.

 

DFS가 같은 출발지 중 도착지가 알파벳순으로 빠른 애를 먼저 대상으로 하여 먼저 답을 완성하게 될 것.

 

전역변수 String fanswer를 null로 해두고, DFS함수 set의 시동을 겁니다.

 

 

public void set(String[][] tickets, boolean[] check, int count, String prev, String[] answer) {
    if(fanswer!=null) return;
    if(count==check.length) {
        if(fanswer==null) fanswer=answer;
    }
    else {
        for(int i=0;i<tickets.length;i++) {
            if(!check[i] && tickets[i][0].equals(prev)) {
                boolean[] newcheck = check.clone();
                newcheck[i] = true;
                String[] newanswer = answer.clone();
                newanswer[count+1] = tickets[i][1];
                set(tickets, newcheck, count+1, tickets[i][1], newanswer);
            }
        }
    }
}

count가 boolean[] check의 크기와 같다면(tickets의 모든 티켓을 소모했다면) 현재 String[] answer를 fanswer로 함.

 

fanswer에 이미 뭔가 들어갔으면 모두 return으로 빠져나옴.

 

!check[i] → 아직 티켓을 사용하지 않았고,

tickets[i][0].equals(prev) → 이 티켓의 출발지가 전단계라면

 

이 티켓을 소모 표시하면서, 답 배열에 적어주면서 반복.

(count가 증가하면서 check 크기만큼되면 모두 사용한 것이 될 것이고,

for를 다 돌더라도 현재상황에서 갈 수 없으면 굳이 함수가 호출되지 않으니 안 될 조합은 거기서 멈춤.)

 

 

모든 도시가 방문 가능한 예제만 주어지니 fanswer는 null이 아닐테고, set을 돌면서 뭔가 답을 얻어나올 것임.