[programmers] 여행경로 (Java)

[문제 - 여행경로]

[코딩테스트 연습 - 깊이/너비 우선 탐색(DFS/BFS) - 여행경로]

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

프로그래머스

 

[접근 방식]

DFS 를 이용하여 문제를 해결하고자 한다.

 

1. 그래프 생성

DFS 탐색을 위한 그래프를 생성해야 한다.

그래프는 " Map<String, PriorityQueue<String>> graph = new HashMap<>(); " 로 구성한다.

String -> 출발하는 공항의 명칭 (ex) "ICN")

PriorityQueue<String> -> 도착 공항의 명칭 저장을 위한 우선순위 큐 (알파벳 순으로 저장)

 

2. 그래프 구성

"tickets" 2차원 배열을 통해 그래프를 구성한다.

 

3. DFS 메서드 구현

"ICN" 을 최초 출발지(루트 노드) 로 하여, 우선순위 큐가 빌때 까지 재귀호출한다.

 

 

[Java 코드]

//https://school.programmers.co.kr/learn/courses/30/lessons/43164
//코딩테스트 연습 - 깊이/너비 우선 탐색(DFS/BFS) - 여행경로


import java.util.*;

class Solution {
    public String[] solution(String[][] tickets) {

        //1. 그래프 생성 
        Map<String, PriorityQueue<String>> graph = new HashMap<>();
        List<String> result = new LinkedList<>(); //경로 저장 리스트

        //2. 그래프 구성
        for (String[] ticket : tickets) {
            graph.computeIfAbsent(ticket[0], k -> new PriorityQueue<>()).add(ticket[1]);
        }

        //DFS 호출을 통한 경로 구성
        dfs("ICN", graph, result);
        return result.toArray(new String[0]); //List -> Array 변환
    }

    private void dfs(String airport, Map<String, PriorityQueue<String>> graph, List<String> result) {
        //'airport' 를 출발지로 하는 도착지 목록
        PriorityQueue<String> destinations = graph.get(airport);
        //도착지를 출발지로 하여 재귀호출
        while (destinations != null && !destinations.isEmpty()) {
            dfs(destinations.poll(), graph, result);
        }
        //DFS 의 리프노드 부터 저장됨으로 역순 저장
        result.add(0, airport);
    }
}

 

 

[Rewind]

1. 어려웠던 점

- 우선 DFS가 해결방법임을 알았으나, 그래프를 어떠한 자료형으로 구성해야 하는지 스스로 깨닫지 못하였다.

 

//1. "map.computeIfAbsent()" 메서드
graph.computeIfAbsent(ticket[0], k -> new PriorityQueue<>()).add(ticket[1]);

만약 ticket[0] 의 키가 존재하지 않는다.

-> 해당 키와 연결된 value 역시 존재하지 않는다.

-> key : ticket[0] 으로 저장, value : new PriorityQueue<>() 로 저장하고 우선순위 큐에 ticket[1] 을 저장한다.

 

//2. List<String> -> String[] 변환
result.toArray(new String[0]);

new String[0] 을 사용하면 result 리스트의 크기와 동일한 String[] 배열로 변환해준다.

 

//3. DFS 로 도출된 노드 역순 저장 이유
result.add(0, airport);

DFS 는 재귀호출로 인해 리프노드 부터 저장됨으로 저장할 값을 result 의 index : 0 자리에 저장하여 역순으로 저장해야 한다.

 

2. 알게된 점

- 위 3가지 메서드 활용법에 대해 알게되었다.

- DFS를 활용하는 한가지 문제에 대해 알게되었다.

- 하나의 그래프 구성 유형에 대해 알게되었다.

 

3. 개선방안

- 문제를 계속 푸는것이 능사인지 모르겠으나, 효율적인 학습 방법을 찾을때 까지 계속해 더 많은 문제를 풀겠다.