[프로그래머스] 여행경로 (07.15)

문제

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

코딩테스트 연습 - 여행경로

 

접근법

백트래킹으로 해결했다.

도착지와 출발지를 비교해가면서 DFS로 배열을 순회한다.

순회를 하면서 모든 경로를 str이라는 배열에 이어붙여주고

모든 티켓을 사용하게 되면 str에 저장된 경로를 리스트에 저장해준다.

제한 사항에서 경로가 2개 이상이라면 알파벳 순으로 하라고 했기 때문에

Collections.sort를 통해서 배열을 알파벳 순으로 정렬해주고 경로를 배열로 바꿔 return 하였다. 

 

코드

import java.util.*;

class Solution {
    private String[][] tickets;
    private int len;
    private boolean[] visited;
    private List<String> res = new ArrayList<>();
    public String[] solution(String[][] tickets) {

        this.tickets = new String[tickets.length][tickets[0].length];
        this.visited = new boolean[tickets.length];
        this.len = tickets.length;
        
        for(int i=0;i<tickets.length;i++){
            for(int j=0;j<tickets[i].length;j++){
                this.tickets[i][j] = tickets[i][j];
            }
        }
        for(int i=0;i<len;i++){
            if(tickets[i][0].equals("ICN")){
                visited[i] = true;
                dfs(tickets[i][1], 0, tickets[i][0] + " ");
                visited[i] = false;
            }
        }

        Collections.sort(res);

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

    private void dfs(String des, int cnt, String str){
        if(cnt == len-1){
            str += des;
            res.add(str);
            return;
        }

        for(int i=0;i<tickets.length;i++){
            if(!visited[i] && tickets[i][0].equals(des)){
                visited[i] = true;
                dfs(tickets[i][1], cnt+1, str + tickets[i][0] + " ");
                visited[i] = false;
            }
        }
    }

}