[프로그래머스 (Java)] 여행경로

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

코딩테스트 연습 - 여행경로

dfs 를 이용해 가능한 모든 경우를 확인하면서 그중 알파벳 순으로 가장 앞서는 답을 구하는 방식입니다.

Collections.min() 의 부분에서 따로 Comparator 객체를 람다를 이용해서 넣은것을 확인할 수 있습니다.

이는 1. 긴 답이 먼저오도록 2. 둘이 길이가 같다면 알파벳 순으로 앞서는 답이 먼저 오도록

순서를 직접 지정하기 위해서 만든 람다함수입니다.

 

만약 class 안에 따로 Set<String> answers 라는 field 를 생성한다면,
모든 tickets 을 활용할 수 있는 답인 경우 answers 에 넣고 마지막에 Collections.min 을 이용해서 구할 수 있습니다.

 

하지만 다른 프로그래밍 언어에서도 쉽게 사용할 수 있도록 함수형 프로그래밍을 지향하였고 다음과 같은 재귀함수로 dfs를 작성했습니다.

import java.util.*;

class Solution {
    public String findPath(String[][] tickets, boolean[] usedTicket, String last) {
        Set<String> pathSet = new HashSet<>();
        for (int i = 0; i < tickets.length; i++) {
            if (!usedTicket[i] && tickets[i][0].equals(last)) {
                usedTicket[i] = true;
                pathSet.add(findPath(tickets, usedTicket, tickets[i][1]));
                usedTicket[i] = false;
            }
        }
        return pathSet.size() == 0
                ? last
                : last + " " + Collections.min(pathSet, (s1, s2) -> s1.length() != s2.length() ? s2.length() - s1.length() : s1.compareTo(s2));
    }


    public String[] solution(String[][] tickets) {
        String[] answer = findPath(tickets, new boolean[tickets.length], "ICN").split(" ");
        return answer;
    }
}