[프로그래머스(Programmers)] 여행경로 (java, DFS)

fantastik·2021년 8월 4일
2
post-thumbnail

안녕하세요. 오늘은 프로그래머스 여행경로 문제를 풀어보려고 합니다.


문제 링크

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

전체 코드

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

public class Solution {
    
    List<String> answer = new ArrayList<>();
    String route = "";
    boolean[] visited;

    public String[] solution(String[][] tickets){
        visited = new boolean[tickets.length];
        dfs(tickets, "ICN", 0);

        Collections.sort(answer);

        return answer.get(0).split(",");
    }

    private void dfs(String[][] tickets, String end, int cnt){
        route += end + ",";

        if (cnt == tickets.length) {
            answer.add(route);
            return;
        }

        for (int i = 0; i < tickets.length; i++) {
            String nextStart = tickets[i][0];
            String nextEnd = tickets[i][1];

            if (nextStart.equals(end) && visited[i] == false) {
                visited[i] = true;
                dfs(tickets, nextEnd, cnt + 1);
                visited[i] = false;
                route = route.substring(0, route.length() - 4);
            }
        }
    }
}

0개의 댓글