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

DFS/BFS 를 통해 푸는 문제

 

 - 탈출 조건 (모든 경로에 도달, 경로를 찾을 수 없을 때)

 - 신경 써야할 중간 조건 (분기점 (=여러 곳에 비행기가 도착할 수 있는 경우의 수, = 중간 지점에서 두 가지의 경로로 진행 가능한 경우)

 - 예외사항 (아예 도달할 수 없는 경우)

 

 

import java.util.*;

class Solution {
    boolean[] checks;
    String[][] tickets;
    List<String> resultList = new ArrayList<>();
    
    void dfs(String lastLocation, List<String> locations) {
        boolean isCompleted = true;
        for(boolean flag: checks) {
            if (!flag) {
                isCompleted = false;
            }
        }
        if(isCompleted) {
            locations.add(lastLocation);
            if(resultList.size() > 0) {
                int index = compareArrayAlphabet(resultList, locations);
                resultList = index > 0 ? locations : resultList;
            } else {
                resultList = locations;   
            }
            return;
        }
        // int targetIdx = -1;
        List<Integer> targetIndices = findTargetLocation(lastLocation);
        if(targetIndices.size() < 0) {
            return;
        } else {
            for(Integer targetIdx: targetIndices) {
                checks[targetIdx] = true;
                List<String> newLocations = new ArrayList<>();
                newLocations.addAll(locations);
                newLocations.add(lastLocation);
                dfs(tickets[targetIdx][1], newLocations);
                checks[targetIdx] = false;
            }
        }
    }
    
    List<Integer> findTargetLocation(String lastLocation) {
        String[] result = null;
        List<Integer> indexArr = new ArrayList<>();
        for(int i=0; i<tickets.length; i++) {
            String[] ticket = tickets[i];
            String departure = ticket[0];
            if(checks[i]) {
                continue;
            }
            if(lastLocation.equals(departure)) {
                indexArr.add(i);
            }
        }
        return indexArr;
    }
    
    int compareArrayAlphabet(List<String> prevArr, List<String> curArr) {
        int resultIdx = 0;
        for(int i=0;i<prevArr.size();i++) {
            String prevElem = prevArr.get(i);
            String curElem = curArr.get(i);
            int compare = prevElem.compareTo(curElem);
            if (compare < 0) {
                resultIdx = 0;
                break;
            } else if (compare > 0) {
                resultIdx = 1;
                break;
            } else {
                continue;
            } 
        }
        return resultIdx;
    }
    
    public String[] solution(String[][] tickets) {
        this.tickets = tickets;
        String startPoint = "ICN";
        for(int i=0; i<tickets.length; i++) {
            String[] ticket = tickets[i];
            if(ticket[0].equals(startPoint)) {
                checks = new boolean[tickets.length];
                checks[i] = true;
                List<String> locations = new ArrayList<>();
                locations.add(ticket[0]);
                dfs(ticket[1], locations);   
            }
        }
        String[] answer = resultList.toArray(new String[0]);
        return answer;
    }
}