오늘의 코테 문제

여행경로 - 프로그래머스

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

public class Solution {
    private static boolean[] visited; // 방문한지 안한지를 체크하는 visited 배열
    private static List<String> result = new ArrayList<>();

    public static String[] solution(String[][] tickets) {
        visited = new boolean[tickets.length];
        
        dfs(0, "ICN", "ICN", tickets);
        Collections.sort(result);
        
        String[] answer = result.get(0).split(" ");
        return answer;
    }

    public static void dfs(int idx, String start, String route, String[][] tickets) {
        if (idx == tickets.length) {
            result.add(route);
            return;
        }

        for (int i = 0; i < tickets.length; i++) {
            if (tickets[i][0].equals(start) && !visited[i]) {
                visited[i] = true;
                dfs(idx + 1, tickets[i][1], route + " " + tickets[i][1], tickets);
                visited[i] = false;
            }
        }
        return;
    }
}

정렬을 어디서 해야하나 고민했는데 리턴값을 정렬해주면 된다. ㅋ

백트래킹 관련 문제였는데 딱 문제를 보자마다 이거 dfs써야하는구나 하는 생각이 들었다.
dfs를 통해서 그래프를 탐색하는 문제였다!

아무래도 DFS와 그래프 ,그리디 모두 내게 취약한 문제였기 때문에 지금 푸는 문제가 딱 내수준 ㅋ

#99클럽 #코딩테스트준비 #개발자취업 #항해99 #TIL