프로그래머스 여행 경로 Java

https://www.acmicpc.net/problem/16929

문제

---

생각하기

---

• 그래프 문제

• 오일러의 경로

동작

String을 사용한 인접 리스트를 만들어야 해서

LinkedHashMap<String, LinkedList<String>> adjList = new LinkedHashMap<>();의 자료구조를 사용했다.

결과

코드

---

Java

import java.util.*;

class Solution {
    static int N;
    
    public List<String> solution(String[][] tickets) {        
        
        // 정렬
        N = tickets.length;
        Arrays.sort(tickets, (o1, o2) -> {
            return o1[0].compareTo(o2[0]);
        });
        
        LinkedHashMap<String, LinkedList<String>> adjList = new LinkedHashMap<>();
        for(int i=0; i<N; i++) {
            adjList.put(tickets[i][0], new LinkedList<>());
        }
        
        for(int i=0; i<N; i++) {
            adjList.get(tickets[i][0]).offer(tickets[i][1]);
            Collections.sort(adjList.get(tickets[i][0]));
        }
                
        
        Stack<String> stack = new Stack<>();
        List<String> list = new ArrayList<>();
        stack.push("ICN");
        
        while(!stack.isEmpty()) {
            String cur = stack.peek();
            
            if(adjList.get(cur) != null && !adjList.get(cur).isEmpty()) {
                String next = adjList.get(cur).removeFirst();
            
                stack.push(next);
            } else {
                list.add(stack.pop());
            }
            
        }
        
        Collections.reverse(list);        
        
        return list;
    } // End of solution()
} // End of Solution class