[프로그래머스] 43164. 여행 경로

[yenzip]

문제 링크

[ASak1104]

43164. 여행 경로

• 언어 : Java
• 코드 : 깃허브
• 성능 : Time: 1.72 ms, Memory: 77.8 MB

Java 풀이

```java import java.util.ArrayList; import java.util.Collections; import java.util.HashMap; import java.util.List; import java.util.Map; import java.util.PriorityQueue; class Solution { static String START = "ICN"; Map> edges = new HashMap<>(10_000); List answer = new ArrayList<>(10_000); public String[] solution(String[][] tickets) { for (String[] ticket : tickets) { String u = ticket[0]; String v = ticket[1]; edges.computeIfAbsent(u, value -> new PriorityQueue<>()).add(v); edges.computeIfAbsent(v, value -> new PriorityQueue<>()); } travel(START); Collections.reverse(answer); return answer.toArray(String[]::new); } void travel(String u) { PriorityQueue edge = edges.get(u); while (!edge.isEmpty()) { travel(edge.poll()); } answer.add(u); } } ```

코멘트

• 39 와 동일한 문제

[yenzip]

43164. 여행 경로

• 언어: JAVA
• 성능:

JAVA 코드 풀이

```java import java.util.*; class Solution { List answer = new ArrayList<>(); boolean[] visited = new boolean[10001]; public boolean dfs(String[][] tickets, String current, int count) { answer.add(current); if(count == tickets.length) { // 모든 항공권 사용 return true; } for(int i = 0; i < tickets.length; i++) { if(tickets[i][0].equals(current) && !visited[i]) { visited[i] = true; if(dfs(tickets, tickets[i][1], count + 1)) { return true; } visited[i] = false; // 백트래킹 answer.remove(answer.size() - 1); // 다른 경로 탐색 } } return false; } public String[] solution(String[][] tickets) { Arrays.sort(tickets, (a, b) -> a[1].compareTo(b[1])); dfs(tickets, "ICN", 0); return answer.toArray(new String[answer.size()]); } } ```

코멘트

• 백트래킹으로 문제를 해결했습니다.
• 테스트케이스 1, 2번이 계속 틀렸는데, 경로가 끊어진 경우에 되돌아가야 하는 부분을 미처 생각하지 못했네요..!