[프로그래머스] 코딩테스트 연습 - 깊이/너비 우선 탐색(DFS/BFS) Level 3 여행경로
Solution.java
import java.util.*;
class Solution {
HashMap<String, ArrayList<String>> hm1;
HashMap<String, ArrayList<Boolean>> hm2;
public String[] solution(String[][] tickets) {
String[] answer = {};
answer = new String[tickets.length + 1];
Arrays.sort(tickets, Comparator.comparing(o -> o[1]));
hm1 = new HashMap<>();
hm2 = new HashMap<>();
for (String[] ticket : tickets) {
ArrayList<String> arr1 = hm1.get(ticket[0]);
ArrayList<Boolean> arr2 = hm2.get(ticket[0]);
if (arr1 == null) {
arr1 = new ArrayList<>();
arr2 = new ArrayList<>();
hm1.put(ticket[0], arr1);
hm2.put(ticket[0], arr2);
}
arr1.add(ticket[1]);
arr2.add(false);
}
ArrayList<String> to = hm1.get("ICN");
ArrayList<Boolean> visited = hm2.get("ICN");
answer[0] = "ICN";
for (int i = 0; i < to.size(); i++) {
visited.set(i, true);
answer[1] = to.get(i);
if (dfs(2, answer)) break;
visited.set(i, false);
}
return answer;
}
boolean dfs(int d, String[] answer) {
if (d == answer.length) return true;
String from = answer[d - 1];
ArrayList<String> to = hm1.get(from);
ArrayList<Boolean> visited = hm2.get(from);
if (to != null) {
for (int i = 0; i < to.size(); i++) {
if (!visited.get(i)) {
visited.set(i, true);
answer[d] = to.get(i);
if (dfs(d + 1, answer)) return true;
visited.set(i, false);
}
}
}
return false;
}
}
import java.util.*;
class Solution {
HashMap<String, ArrayList<String>> hm1;
HashMap<String, ArrayList<Boolean>> hm2;
public String[] solution(String[][] tickets) {
String[] answer = {};
answer = new String[tickets.length + 1];
Arrays.sort(tickets, Comparator.comparing(o -> o[1]));
hm1 = new HashMap<>();
hm2 = new HashMap<>();
for (String[] ticket : tickets) {
ArrayList<String> arr1 = hm1.get(ticket[0]);
ArrayList<Boolean> arr2 = hm2.get(ticket[0]);
if (arr1 == null) {
arr1 = new ArrayList<>();
arr2 = new ArrayList<>();
hm1.put(ticket[0], arr1);
hm2.put(ticket[0], arr2);
}
arr1.add(ticket[1]);
arr2.add(false);
}
ArrayList<String> to = hm1.get("ICN");
ArrayList<Boolean> visited = hm2.get("ICN");
answer[0] = "ICN";
for (int i = 0; i < to.size(); i++) {
visited.set(i, true);
answer[1] = to.get(i);
if (dfs(2, answer)) break;
visited.set(i, false);
}
return answer;
}
boolean dfs(int d, String[] answer) {
if (d == answer.length) return true;
String from = answer[d - 1];
ArrayList<String> to = hm1.get(from);
ArrayList<Boolean> visited = hm2.get(from);
if (to != null) {
for (int i = 0; i < to.size(); i++) {
if (!visited.get(i)) {
visited.set(i, true);
answer[d] = to.get(i);
if (dfs(d + 1, answer)) return true;
visited.set(i, false);
}
}
}
return false;
}
}
간단한 DFS 문제였지만 예외상황을 생각하지 못해 런타임 에러가 떴었다.
다른 사람이 올려준 테스트 케이스를 보고 예외상황을 해결하여 풀었다.
언제나 예외상황은 생각하기 힘든 것 같다.
출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges
Author And Source
이 문제에 관하여([프로그래머스] 코딩테스트 연습 - 깊이/너비 우선 탐색(DFS/BFS) Level 3 여행경로), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@hye07on11/프로그래머스-코딩테스트-연습-깊이너비-우선-탐색DFSBFS-Level-3-여행경로저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)