[99클럽 코테 스터디 4일차 TIL] DFS

📖 오늘의 학습 키워드
DFS

오늘의 회고

문제

[여행경로]
https://school.programmers.co.kr/learn/courses/30/lessons/43164

나의 해결

import java.util.*;
class Solution {
    public String[] answer;
    public boolean[] visited;
    public int len;
    public String[] solution(String[][] tickets) {
        len = tickets.length;
        answer = new String[len+1];
        visited = new boolean[len];
        String[] temp = new String[len+1];
        temp[0] = "ICN";
        dfs(1, "ICN",  temp, tickets);
        return answer;
    }
    public void dfs(int level, String from, String[] temp, String[][] tickets) {
        if(level == len+1) {
            if(answer[0] == null) {
                answer = temp.clone();
            }
            else{
                for(int i = 0; i < len; i++) {
                    if(temp[i].compareTo(answer[i]) < 0) {
                        answer = temp.clone();
                        break;
                    } else if(answer[i].compareTo(temp[i]) < 0) {
                        break;
                    }
                }
            }
            return;
        }
        for(int i = 0; i < len; i++) {
            if(tickets[i][0].equals(from) && !visited[i]) {
                visited[i] = true;
                temp[level] = tickets[i][1];
                dfs(level+1, tickets[i][1], temp, tickets);
                visited[i] = false;
            }
        }
    }
}

1. DFS를 이용해서 주어진 모든 항공권을 사용해 만들 수 있는 모든 여행 경로를 찾는다.
2. 여행 경로를 새로 찾을 때마다 정답과 비교하여 새로 찾은 경로의 알파벳 순서가 앞서다면 기존의 정답을 새로 찾은 경로로 변경한다.

새로 학습한 내용

DFS를 복습할 수 있었다.