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

여행경로

해결 방법

1트

각 비행 경로(String)를 숫자(Integer)로 저장하는 Map을 만들고 이를 인접 리스트로 만들어서 해결하려고 했으나 실패!!! ㅠ0ㅠ

2트

우선순위 큐를 사용하는 BFS로 탐색하면 될거라고 판단했지만, 실패!

3트

아! 위상 정렬(topological)을 사용하면 되는건가….!! 라고 생각했지만,
사이클이 발생할 수 도 있기 때문에 실패!

위상 정렬은 사이클이 없는 방향 그래프에서 노드 순서를 찾는 알고리즘

참고
그래프에 사이클이 존재하면…?🤔
노드 간의 순서를 명확하게 정의할 수 없기 때문에 위상 정렬 사용불가..!

4트

결국 구글링을 통해 문제를 해결했습니다.
해결 방법은 DFS를 사용하면 됩니다.

DFS를 사용하여 원하는 깊이 까지 탐색이 완료된 경로를 우선순위 큐(PriorityQueue)에 저장합니다.
우선 순위 큐에 저장된 경로를 반환 하면 됩니다.

DFS에서 큐가 왜 나와? 😲

• 문제에서 만일 가능한 경로가 2개 이상일 경우 알파벳 순서가 앞서는 경로를 return 하라고 했기 때문 입니다.^^

입출력 예제2번은 다음과 같은 경로를 형성할 수 있습니다.

// 입력 예제2
[["ICN", "SFO"], 
["ICN", "ATL"], 
["SFO", "ATL"], 
["ATL", "ICN"], 
["ATL","SFO"]]

정리

DFS는 가중치가 1인 그래프에서 모든 조합을 검색하는 것을 고려하는 기법(깊이를 이용한다.)
해당 분기를 완벽하게 탐색한다.
탐색에 있어 경로에 대한 정보가 필요할 때 사용한다.

BFS는 가중치가 1인 그래프에서 최단 경로를 찾는 기법(경로를 찾으면 탈출)
인접한 모든 노드를 먼저 탐색한다.

참고
트리에서도 DFS를 이용하여 경로를 찾을 수 있습니다.
가중치가 있는 트리에서 노드와 노드간의 최대거리 또는 최단거리를 구할 때 DFS를 사용할 수 있습니다.
백준 1967: 트리의 지름(Java)

• 모든 그래프 탐색

  • DFS, BFS

• 경로의 특징을 저장

  • DFS

• 최단거리

  • BFS

풀이

class Solution {
    public String[] solution(String[][] tickets) {
        Queue<String> pq = new PriorityQueue<>();
        boolean[] visited = new boolean[tickets.length];
        dfs(pq, tickets, visited, 0, "ICN", "ICN");

        String[] split = pq.peek().split("->");

        return split;
    }

    private void dfs(Queue<String> pq, String[][] tickets, boolean[] visited, int depth, String start, String path) {

        // 탐색을 원하는 깊이에 도달하면
        if(tickets.length == depth) {
            // 지금까지 탐색한 경로를 저장
            pq.offer(path);
            return;
        }

        for(int i = 0; i < tickets.length; i++) {
            // 방문 이력이 없고, 출발 도시(start)가 여행 경로의 도착지(tickets[i][0])인 경우
            if(!visited[i] && start.equals(tickets[i][0])) {
                // 방문
                visited[i] = true;
                // dfs 수행
                dfs(pq, tickets, visited, depth + 1, tickets[i][1], path + "->" + tickets[i][1]);
                // 모든 dfs를 수행했으면 방문 이력 초기화(모든 경우의 수를 고려한 경로를 다 방문하기 위함)
                visited[i] = false;
            }
        }
    }
}