Java - [프로그래머스]43164-여행경로

출처

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

문제

주어진 항공권을 이용해 갈수 있는 모든 경로 중 알파벳 순으로 가장 빠른 경로를 구하는 문제입니다. 경로가 선택되는 순서에 따라 답이 달라집니다.

풀이

이 문제를 어떻게 접근할지 고민하다가 가장 간단한 방법이 완전 탐색이라고 생각하였습니다. ArrayList를 이용하여 구해진 경로를 넣어둘 것이고 ticket 사용여부를 알기 위한 boolean배열을 사용하였습니다. List에는 경로를 이어붙인 문자열 path값을 넣어둡니다. dfs를 통해 구해줄 것인데, 변수로는 tickets, 경로를 붙인 문자열 path, 현재 위치, 현재까지 사용한 티켓의 갯수 depth를 가지고 있습니다.

맨 처음 시작지점은 문제에 나와있는 것 처럼 "ICN"으로 설정해주었고, 이 티켓이 사용되었는지, 현재 위치와 다음 위치를 비교하여 depth가 티켓배열의 길이와 같아지면 종료하도록 하였습니다. 탐색이 끝나면 모든 경로의 수는 list에 담기게 되며, sort를 진행하여 알파벳 순으로 가장 빠른 0번째 인덱스가 정답이 됩니다. 해당 인덱스를 String[]으로 바꾸어 리턴하면 끝입니다.

코드

import java.util.*;
class Solution {
    List<String> list = new ArrayList<>();
    boolean[] visited;
    public void dfs(String[][] tickets, String path, String key, int depth) {
        if(depth == visited.length) {
            list.add(path);
            return;
        }
        for(int i = 0; i < tickets.length; i++) {
            if(tickets[i][0].equals(key) && !visited[i]) {
                visited[i] = true;
                dfs(tickets, path + " " + tickets[i][1], tickets[i][1], depth + 1);
                visited[i] = false;
            }
        }
    }
    
    public String[] solution(String[][] tickets) {
        visited = new boolean[tickets.length];
        dfs(tickets, "ICN", "ICN", 0);
        Collections.sort(list);
        System.out.print(list.size());
        return list.get(0).split(" ");
    }
}

풀이 2

정렬을 사용하는 것이 아닌, 저장시에 알파벳 순으로 비교하여 String으로 바로 저장하게 하는 방법도 있습니다.

"ICN"으로 시작하기에 초기값은 "J"로 잡아두고, 경로가 하나 완성될 때 마다 compareTo()메서드로 비교하여 알파벳 순으로 앞선것을 저장하도록 하였습니다.

코드 2

import java.util.*;
class Solution {
    String result = "J";
    boolean[] visited;
    public void dfs(String[][] tickets, String path, String key, int depth) {
        if(depth == visited.length) {
            result = result.compareTo(path) > 0 ? path : result;
            return;
        }
        for(int i = 0; i < tickets.length; i++) {
            if(tickets[i][0].equals(key) && !visited[i]) {
                visited[i] = true;
                dfs(tickets, path + " " + tickets[i][1], tickets[i][1], depth + 1);
                visited[i] = false;
            }
        }
    }
    
    public String[] solution(String[][] tickets) {
        visited = new boolean[tickets.length];
        dfs(tickets, "ICN", "ICN", 0);
        return result.split(" ");
    }
}