[프로그래머스, 자바] DFS 여행경로

프로그래머스 3단계 여행경로 문제

 url : https://programmers.co.kr/learn/courses/30/lessons/43164?language=java

문제설명

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

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

제한사항

모든 공항은 알파벳 대문자 3글자로 이루어집니다. 주어진 공항 수는 3개 이상 10,000개 이하입니다.

tickets의 각 행 [a, b]는 a 공항에서 b 공항으로 가는 항공권이 있다는 의미입니다.주어진 항공권은 모두 사용해야 합니다.

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

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

입출력 예

prices	return
[[ICN, SFO], [ICN, ATL], [SFO, ATL], [ATL, ICN], [ATL,SFO]]	[ICN, ATL, ICN, SFO, ATL, SFO]

입출력 예 설명

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

자바코드

        
package Q43164;

import java.util.*;

class Solution {
    public String[] solution(String[][] tickets) {
        // 출발지 초기화 //
        List nodeList = new ArrayList<>();
        for (int i = 0; i < tickets.length; i++)
            nodeList.add(new Node(tickets[i][0], tickets[i][1]));

        Collections.sort(nodeList, ((o1, o2) -> o1.departure.compareTo((o2.departure)) != 0
                ? o1.departure.compareTo((o2.departure)) : o1.destination.compareTo(o2.destination)));

        // ICN으로 시작된 출발점 설정 //
        List departures = new ArrayList<>();
        for (Node node : nodeList)
            if(node.departure.equals("ICN"))
                departures.add(node);

        // DFS //
        for (Node node : departures) {
            node.index = 0;
            if(dfs(nodeList, node, 1)) break;
        }

        return createArray(nodeList);
    }

    public String[] createArray(List nodeList) {
        // index 순차적으로 값을 넣기 위해 //
        Collections.sort(nodeList, (o1, o2) -> o1.index > o2.index ? 1 : -1);

        String[] answer = new String[nodeList.size() + 1];
        answer[0] = nodeList.get(0).departure;
        answer[1] = nodeList.get(0).destination;
        for (int i = 1; i < nodeList.size(); i++)
            answer[i + 1] = nodeList.get(i).destination;

        return answer;
    }

    public boolean dfs(List tickets, Node departure, int idx) {
        boolean stop = false;
        if(idx == tickets.size())
            return true;

        for (Node ticket : tickets) {
            if(ticket.index < 0 && departure.isAdjacent(ticket)) {
                ticket.index = idx;
                if((stop = dfs(tickets, ticket, idx + 1))) break;
            }
        }

        // 잘못된 경로 일 경우, 현재 경로는 취소하기 위한 로직 //
        if(!stop)
            departure.index = -1;

        return stop;
    }

    public class Node {
        private String departure;
        private String destination;
        private int index = -1;

        public Node(String departure, String destination) {
            this.departure = departure;
            this.destination = destination;
        }

        public boolean isAdjacent(Node other) {
            return this.destination.equals(other.departure);
        }
    }
}

문제설명

프로그래머스 DFS/BFS 마지막 문제였다. 이 문제에서 출발지가 항상 ICN 이라는 것을 명심해야 한다. (이 부분을 간과해서... 마지막에 계속 오류가 났다.)

이 문제는 항상 모든 도시를 방문할 수 있게 입력값이 주어지고, 모든 도시를 방문할 수 있는 경우가 복수개 가능하다. 

그렇기 때문에 처음에 도시의 출발지, 목적지의 알파벳순으로 정렬을 했다. 그렇기 때문에 DFS를 했을 때, 가장 먼저 나오는 정답이 모든 도시를 방문도 할 수 

있으며, 동시에 복수개의 답이 나왔을 때도 알파벳의 오름차순으로 나오게 되는 것이다. 그런 제어를 위해서 DFS 재귀를 돌때, boolean stop을 이용해서 

제어를 한다. 그리고 해당 경로에서 모든 경로를 가지 못한다고 하면, 취소하기 위한 로직도 존재한다.

DFS 문제를 풀 때, 방문유무를 판단하는 배열이 항상 필요한데, 정렬을 해버렸기 때문에 index를 통해 구분하는 것이 쉽지 않을 거라 생각해서, 각각의 Node에

index값을 이용해서 방문유무를 판단했다. 만약 index가 -1이면 아직 방문을 하지 않는 것이고, 0이상이면 방문을 이미 한 것이다. 그리고 동시에 해당 index는

방문순서를 나타내기도 한다.

다 풀고나면 어렵지 않는 문제인데, 풀때는 정말 어려웠다. 완전히 이해가 되지않는것보다 알거 같으면서도 뭔가 알지 못하는게 제일 어려운 것 같다.

지금 내가 무슨 말을 하고 있는거지?