[프로그래머스/Java] 여행경로(BFS/DFS) 풀이

프로그래머스 알고리즘 고득점 Kit 문제들 중 BFS, DFS 파트에 해당하는 '여행경로' 문제를 풀어보았다.

https://school.programmers.co.kr/learn/courses/30/lessons/43164

프로그래머스

 

  모든 티켓을 사용해야 하므로, 즉 모든 경로를 거쳐야 하므로, BFS가 아닌 DFS를 사용해야 한다는 것을 알 수 있다. 그리고 "ICN"으로부터 시작해야 하기 때문에, 재귀의 초기 조건을 "ICN"으로부터 출발하는 것으로 설정하고 출발지를 바꾸어가며 재귀를 한다. 재귀의 중단조건은 answer list의 크기인데, (tickets 배열 크기 + 1)개의 공항이 있기 때문에, 이 공항들을 모두 담았는지를 중단 조건으로 담는다. 중단 조건을 먼저 확인하지 않고, answr list에 from을 먼저 추가하는 이유는 from은 이미 방문하지 않았음이 재귀 함수를 호출하기 전 증명되었기 때문이다.

 그리고 반복문을 통해 현재 from에 해당하는 공항을 출발점으로 가진 티켓을 찾고, 재귀 함수로 dfs 순회를 했을 때 모두 돌 수 있는 경우 true를, 아닌 경우 false를 리턴받아, 반복문을 계속 수행할지 아니면 중단하고 true를 리턴할지를 결정한다. 반복문을 모두 돌 동안 from과 같은 출발지를 찾지 못했다면 이 순회 순서로는 모든 공항을 순회할 수 없음을 의미하므로, 마지막 요소를 지우고 false를 리턴한다.

 main 함수에서는 ticket를 도착지 알파벳 순으로 정렬해주는데, 만약 방법이 여러 가지일 경우, 알파벳 순이 우선시되어야 한다는 조건 때문이다.

import java.util.*;

class Solution {
    public boolean dfs(String from, String[][] tickets, List<String> answer) {
        answer.add(from);
        if (answer.size() > tickets.length) return true;

        for (String[] t : tickets) {
            if (t[0].equals(from)) {
                t[0] = "";
                if (dfs(t[1], tickets, answer)) return true;
                else t[0] = from;
            }
        }
        
        answer.remove(answer.size()-1);
        return false;
    }
    
    public String[] solution(String[][] tickets) {
        List<String> answer = new ArrayList<>();
        Arrays.sort(tickets, (a, b) -> a[1].compareTo(b[1]));
        
        dfs("ICN", tickets, answer);
        return answer.toArray(new String[0]);
    }
}