DFS/BFS>여행경로[프로그래머스-JAVA]

📝문제

📝알고리즘

//티켓을 도착지를 기준으로 알파벳 순으로 정렬
//출발지를 "ICN"으로 해서 DFS 탐색을 시작하고
//ArrayList을 String[] 배열로 변환하여 반환
//dfs 메서드는 다음과 같이 작성
//티켓을 다 사용해서 count랑 tickets.length가 같으면 마지막 도착지 추가 후 종료
//현재 공항에서 출발할 수 있는 티켓을 탐색해서
//방문하지 않았고 출발지가 현재 위치와 동일한 경우에 방문했다고 기록하고 경로에 현재 공항 추가
//count+1해서 목적지 탐색하고
//티켓을 다 썼으면 리턴하고 그렇지 않으면 백트래킹

❌틀린 코드

import java.util.*;

class Solution {
    
    private boolean[] visited;
    private ArrayList<String> route = new ArrayList<>();
    private String[][] tickets;

    private void dfs(String now, int count) {
        if (count == tickets.length) {
            route.add(now);
            return;
        }

        for (int i = 0; i < tickets.length; i++) {
            if (!visited[i] && tickets[i][0].equals(now)) {
                visited[i] = true;
                route.add(now);
                dfs(tickets[i][1], count + 1);
                if (route.size() == tickets.length + 1){
                    return;
                }
            }
        }
    }

    public String[] solution(String[][] tickets) {
        this.tickets = tickets;
        visited = new boolean[tickets.length];

        Arrays.sort(tickets, Comparator.comparing(ticket -> ticket[1]));

        dfs("ICN", 0);
        return route.toArray(new String[0]);
    }
}

📝틀린 이유

➡️백트래킹이 제대로 작동하지 않게 코드를 짰음

📝수정한 코드

import java.util.*;

class Solution {
    
    private boolean[] visited;
    private ArrayList<String> route = new ArrayList<>();
    private String[][] tickets;

    private void dfs(String now, int count) {
        if (count == tickets.length) {
            route.add(now);
            return;
        }

        for (int i = 0; i < tickets.length; i++) {
            if (!visited[i] && tickets[i][0].equals(now)) {
                visited[i] = true;
                route.add(now);
                dfs(tickets[i][1], count + 1);
                if (route.size() == tickets.length + 1){
                    return;
                }
                route.remove(route.size() - 1);
                visited[i] = false;
            }
        }
    }

    public String[] solution(String[][] tickets) {
        this.tickets = tickets;
        visited = new boolean[tickets.length];

        Arrays.sort(tickets, Comparator.comparing(ticket -> ticket[1]));

        dfs("ICN", 0);
        return route.toArray(new String[0]);
    }
}

📌기록하고 싶은 내용

배열의 각 요소에 대해 정렬 기준을 적용하고 싶을 때 ➡️ Arrays.sort(배열, Comparator.comparing(정렬 기준)); 쓰기