[프로그래머스 자바] 여행경로 (Lv.3)

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

프로그래머스

 

import java.util.*;

class Solution {
    
    String[][] tickets;
    boolean[] visited;
    List<String> paths = new ArrayList<>();
    
    public String[] solution(String[][] tickets) {
        
        this.tickets = tickets;
        visited = new boolean[tickets.length];
        
        dfs(0, "ICN", "ICN");
        
        Collections.sort(paths);
        
        return paths.get(0).split(" ");
    }
    
    void dfs(int depth, String now, String path) {
        if (depth == tickets.length) {
            paths.add(path);
            return;
        }
        
        for (int i = 0; i < tickets.length; i++) {
            String start = tickets[i][0];
            String next = tickets[i][1];
                
            if (now.equals(start) && !visited[i]) {
                visited[i] = true;
                dfs(depth + 1, next, path + " " + next);
                visited[i] = false;
            }
        }
    }
}

 

우선 Solution 객체 내에 tickets, visited 변수를 선언해주었다. tickets는 출발지와 도착지가 적혀있는 티켓 정보를 가진 이중 배열이고, visited는 각 장소의 방문 여부를 체크하는 용도의 변수다. 

 

dfs로 완전탐색하여 갈 수 있는 경로를 모두 탐색하여 paths 에 넣어두었고, 이를 정렬하여 사전순으로 맞춘 후, 첫 번째 것을 가져온다. 

그리고 paths 리스트에는 각 장소를 공백을 기준으로 하나의 문자열로 되어있는데, 이를 split(" ") 으로 배열로 나누어서 제출해주었다. 

 

dfs에서는 아래에 for 문을 돌면서 path를 공백으로 구분하며 장소를 추가하면서 dfs를 돌고, 모든 티켓을 돌면 paths에 path를 넣어서 리턴한다.