[자바 알고리즘 인터뷰] 12장 그래프 (8) 여행 경로

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

프로그래머스

 

 

 

 

 

풀이 1) 일정 그래프 반복 DFS

 

2024.05.17 - [Java/알고리즘] - [자바 알고리즘 인터뷰] 12장 그래프 (7) 일정 재구성

[자바 알고리즘 인터뷰] 12장 그래프 (7) 일정 재구성

 

- 위 문제와 동일하게 진행 

- 마지막에 String[]으로 변환하기 위해서 toArray() 메소드 활용 

- toArray() 메소드는 자료형을 파라미터로 전달하면 해당 배열로 리턴해준다.

- 또한 크기를 0으로 지정하면 나중에 JVM이 크기에 맞춰서 알아서 실행을 최적화한다. 

 

import java.util.*;

class Solution {
    public String[] solution(String[][] tickets) {
        Map<String,PriorityQueue<String>> fromToMap = new HashMap<>();
        
        //여행 일정을 from->to 형태의 그래프로 구성
        for(String[] ticket : tickets)
        {
            //값이 존재하지 않을 경우 빈 우선순위 큐 생성
            fromToMap.putIfAbsent(ticket[0], new PriorityQueue<>());
            //목적지 to 추가, 우선순위 큐이므로 to는 항상 사전 어휘순으로 정렬된다.
            fromToMap.get(ticket[0]).add(ticket[1]);
        }
        
        List<String>answer = new LinkedList<>();
        Deque<String> stack = new ArrayDeque<>();
        
        //출발지 삽입
        stack.push("ICN");
        while(!stack.isEmpty())
        {
            //스택에서 추출될 값을 출발지로 한 도착지 처리
            while(fromToMap.containsKey(stack.getFirst())&&!fromToMap.get(stack.getFirst()).isEmpty())
            {
                //여러 도착지 중 사전 어휘순으로 추출해 스택에 삽입
                stack.push(fromToMap.get(stack.getFirst()).poll());
            }
            
            //위 반복문이 모두 실행된 이후에는 스택에서 값이 하나씩 추출되어 정답으로 구성된다. 
            answer.add(0,stack.pop());
        }
        
        //String[]으로 변환
        return answer.toArray(new String[0]);

    }
}