99클럽 코테 스터디 34일차 TIL / 여행 경로(프로그래머스)

오늘의 학습 키워드

   - 알고리즘

   - 구현

   - dfs

공부한 내용 본인의 언어로 정리하기

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

조금 까다롭게 문자열을 다뤄야 하는 dfs 문제를 풀었다.

 

풀이 과정은 다음과 같다.

1. 티켓을 모두 사용해야 하므로 dfs에서 방문 처리는 티켓의 인덱스로 사용

2. dfs 로직을 돌며 만약 깊이가 티켓과 동일하다면 해당 여행 경로를 list에 추가

3. 알파벳 순으로 가장 먼저 나오는 경로를 사용해야 하므로 리스트를 정렬하여 0번째 인덱스 값 반환

 

풀이는 다음과 같다.

import java.util.*;

class Solution {
    
    int ticketLen;
    String[][] tickets;
    ArrayList<String> resultList;
    boolean[] visit;

    public String[] solution(String[][] tickets) {

        ticketLen = tickets.length;
        visit = new boolean[ticketLen];
        
        this.tickets = tickets;

        resultList = new ArrayList<>();
        dfs("ICN", 0, "ICN ");
        Collections.sort(resultList);

        return resultList.get(0).split(" ");
    }

    void dfs(String cur, int depth, String visitStr) {

        if (depth == ticketLen) {
            resultList.add(visitStr);
            return;
        }

        StringTokenizer st;
        
        for (int i = 0; i < ticketLen; i++) {
            
            if (visit[i]) continue;

            String[] ticket = tickets[i];
            String from = ticket[0];
            if (!Objects.equals(cur, from)) continue;
            visit[i] = true;
            
            String to = ticket[1];
            dfs(to, depth + 1, visitStr + to + " ");
            visit[i] = false;
            
        }
    }
}