[프로그래머스] 코딩테스트 연습 - 깊이/너비 우선 탐색(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;
    }
}

간단한 DFS 문제였지만 예외상황을 생각하지 못해 런타임 에러가 떴었다.

다른 사람이 올려준 테스트 케이스를 보고 예외상황을 해결하여 풀었다.

언제나 예외상황은 생각하기 힘든 것 같다.

출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges

좋은 웹페이지 즐겨찾기