[프로그래머스 | Java Lv.3] [복습] 여행 경로 (dfs/bfs)

문제

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

프로그래머스

 

접근

 

https://xoxoxoxox.tistory.com/247 단어변환 문제랑 유사했던 문제! 

위에서 삽질했던 게 여기서 쓰였다

path를 저장했어야 했던 것!

 

그리고 잘 이용하면 좋을 코드는 

path.split(" ");

이렇게 했을 때 " "  를 기준으로 배열로 저장된다. 

그래서 이번 문제에서 Path를 "ICN JFK ..." 이런 식으로 하나의 String으로 저장하게 한 다음 배열로 반환해야 하니까 split을 사용하면 간편하게 풀 수 있다. 

---

최종 코드

package week6.baek.dfsbfs;

import java.util.ArrayList;
import java.util.Collections;

public class TravelRoute {
    static boolean[] used;
    static ArrayList<String> result;

    public static void dfs(String[][] tickets, String now, int depth, String path){
        if(depth == tickets.length){
            System.out.println(path);
            result.add(path);
        }

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

    public static String[] solution(String[][] tickets) {
        result = new ArrayList<>();

        for (int i = 0; i < tickets.length; i++) {
            if(tickets[i][0].equals("ICN")) {
                used = new boolean[tickets.length];
                used[i] = true;
                dfs(tickets, tickets[i][1], 1, "ICN " + tickets[i][1] + " ");
            }
        }

        Collections.sort(result);
        String path = result.get(0);
        return path.split(" ");
    }

    public static void main(String[] args) {
        String[][] tickets = {{"ICN", "JFK"}, {"HND", "IAD"}, {"JFK", "HND"}};
        solution(tickets);
    }
}