[프로그래머스] Lv.3 여행 경로

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

프로그래머스

 

사용 알고리즘

• DFS
• 백트래킹

 

풀이

import java.util.*;
class Solution {
    static List<String> res = new ArrayList<>();
    static boolean [] visited;
    public String[] solution(String[][] tickets) {
        visited = new boolean[tickets.length];
        dfs("ICN", "ICN", 0, tickets);
        Collections.sort(res);        
        String [] answer = res.get(0).split(" ");
        return answer;
    }
    
    public void dfs(String start, String path, int depth, String[][] tickets) {
        if (depth == tickets.length) { // 종료 조건 -> 모든 티켓을 다 쓴 경우
            res.add(path);
            return;
        }
        
        for(int i = 0; i < tickets.length; i++) {
            String next = tickets[i][1];
            if (!visited[i] && start.equals(tickets[i][0])) {
                visited[i] = true;
                dfs(next, path + " " + next, depth + 1, tickets);
                visited[i] = false;
            }
        }
    }
}

 

회고

 

일단, 처음에 List<List<String>> 형태에 모든 정점들을 저장하려고 했지만, 문자열을 인덱스로 사용한다면 매우 복잡해진다. 

 

고민하다가 답지를 참고했더니, 백트래킹 방법으로 풀이를 했고 다른 문제들에 비해서 조건들을 따질것이 좀 있었다.

• 항상 ICN에서 출발
• 주어진 항공권은 모두 사용해야 함
• 모든 도시를 방문해야 함

dfs("ICN", "ICN", 0, tickets);

void dfs(String start, String path, int depth, String[][] tickets)

 

DFS의 파라미터들은 이렇게 구성되어 있는데,

• start: 출발 장소
• path: 여행 경로들을 저장
• depth: 간선의 길이. 문제에서 주어진 항공권을 모두 사용해야 한다는 것은 주어진 간선의 길이만큼 백트래킹을 돌려야 한다는 것을 의미한다.
• tickets: 문제에서 주어진 배열

 

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

 

백트래킹의 로직을 살펴보면, 다음 dfs 메서드가 실행될 때, 현재 있는 공항을 다음 공항으로 시작점을 업데이트 해주고, depth를 증가시켜준다. path에는 다음 공항들을 더해줘서 전체 경로를 저장해주도록 구현했다.

 

이해가 안되는 부분은 start.equals(ticket[i][0]) 여기였는데, 자세히 살펴보면

 

문제에서 예제가 이렇게 주어졌을 때,

[["ICN", "JFK"], ["HND", "IAD"], ["JFK", "HND"]]

 

ICN에서 시작을 무조건 해야하니 ICN -> JFK로 무조건 방문할 수밖에 없다.

 

하지만, 저 조건이 없다면

ICN HND IAD JFK
ICN HND JFK IAD
ICN IAD HND JFK
ICN IAD JFK HND
ICN JFK HND IAD
ICN JFK IAD HND

 

이런식으로 모든 조합을 뽑아내게 된다. 백트래킹이 한번 돌고 start가 next인 "JFK"로 업데이트 되었을 때, target 배열에서 시작점도 무조건 동일해야 한다.

 

마지막으로, 알파벳 순으로 정렬을 해야 했는데 sort를 해주면 리스트의 첫번째 값이 정렬된 방문 순서가 저장되어 배열로 바꿔주면 된다.

한번 더 풀어봐야겠다