문제

프로그래머스 - 여행경로

요약

ICN부터 시작되는 전체 여행경로를 출력하라.
단, 2개 이상의 경로가 나오는 경우 알파벳 순서가 빠른 경로를 출력할 것

접근

무조건 "ICN"부터 시작하니까 ICN이 루트 노드가 되는 트리를 탐색하는 것으로 접근을 시작했다.

테스트 코드를 손으로 풀어봤을 때, 이미지와 같은 경로가 나올 수 있도록 구현한다고 생각을 하고, 이를 직접 알고리즘으로 구현했다.

알고리즘

1. 시작: "ICN" 출발 항공권을 찾아 방문 처리 후 DFS 탐색 시작

2. 조건 확인: DFS 내에서 현재 도시(nextCity)와 티켓의 출발지가 같은 미방문 티켓 탐색

3. DFS 진행: 일치하는 티켓을 방문 처리하고 경로(path)에 추가한 뒤, depth를 1 늘려 재귀 호출

4. 백트래킹: 끝까지 가지 못하고 막혔다면, 다른 길을 찾기 위해 방문 해제(visited=false) 및 현재 경로에서 제거

5. 종료 및 갱신: depth가 전체 티켓 수와 같아지면 완성된 경로 반환. 기존 정답이 존재한다면 알파벳 사전순 비교를 통해 조건에 맞는 답으로 갱신

최종 코드

import java.util.*;

class Solution {
    String[][] tickets;
    // 정답 배열
    String[] answer;
    // 총 티켓 개수
    int len;
    // 방문 여부 확인
    boolean[] visited;
    // 누적 경로 저장
    List<String> path;
    
    public String[] solution(String[][] tickets) {
        this.tickets = tickets;
        this.len = tickets.length;
        answer = new String[len+1];
        
        for (int i = 0; i < len; i++) {
            // 방문 배열 초기화
            this.visited = new boolean[len];
            // 누적 경로 초기화
            this.path = new ArrayList<>();
            if (tickets[i][0].equals("ICN")) {
                visited[i] = true;
                path.add(tickets[i][0]);
                path.add(tickets[i][1]);
                findPath(1, tickets[i][1]);
            }
        }
        
        return answer;
    }
    
    // 방문한 나라 수(depth)와 다음 도시를 매개변수(nextCity)로 받음
    public void findPath(int depth, String nextCity) {
        // 모든 배열 방문 시 종료
        if (depth >= len) {
            if (answer[0] == null) {
                answer = path.toArray(new String[0]);
            }
            // 알파벳 순서로 비교
            for (int i = 0; i < depth; i++) {
                // answer가 사전순으로 더 빠르다 (음수)
                if (answer[i].compareTo(path.get(i)) < 0) {
                    break;
                }
                // answer가 사전순으로 더 느리다 (양수)
                else if (answer[i].compareTo(path.get(i)) > 0) {
                    answer = path.toArray(new String[0]);
                    break;
                }
            }
            return;
        }
        
        for (int i = 0; i < len; i++) {
            if (!visited[i] && tickets[i][0].equals(nextCity)) {
                visited[i] = true;
                path.add(tickets[i][1]);
                findPath(depth+1, tickets[i][1]);
                // 가지치기로 다른 경우를 찾기 위해 방문 배열을 false로 처리
                visited[i] = false;
                // 추가한 경로 제거
                path.remove(path.size()-1);
            }
        }
        // 방문 가능한 배열 없을 시 종료
        return;
    }
}

어려웠던 점

• List 자료형을 배열로 바꾸는 코드가 자꾸 생각이 안난다... 직접 생각하는데 5분씩은 걸린다. 이를 외울 것!
  ➡️ list.toArray(new String[0])
• String[]을 new로 생성하면 null이 저장된다는걸 이제 처음 피부로 깨달음... 어쩐지 .eqauls("")로 하니까 자꾸 널포인터익셉션 터지더니...
  ➡️ String은 String Pool에서 관리하는게 아니면 객체로 생성되기 때문에 null로 초기화가 된다!
• dfs에서 visited를 false로 바꿨을 때, 지금 추가했던 path 경로도 제거해줘야한다! (백트래킹해야하니까 이전 상태로 돌려야 한다!)