99클럽 코테 스터디 34일차 TIL [DFS, BFS]

- 오늘의 학습 키워드 : DFS, BFS

[문제 이름 : 여행경로 (프로그래머스, Lv 3)]

문제 url : https://school.programmers.co.kr/learn/courses/30/lessons/43164

내가 작성한 코드는 아래와 같다.

import java.util.*;

class Solution {
    static ArrayList<String> answer = new ArrayList<>();
    static Map<String, List<String>> map = new HashMap<>();
    static int totalTickets;
    static boolean isComplete = false;
    
    public String[] solution(String[][] tickets) {
        // 총 배열 길이
        totalTickets = tickets.length + 1;
        
        // 티켓 정보 저장
        for(String[] ticket : tickets) {
            String start = ticket[0];
            String end = ticket[1];
            
            if(!map.containsKey(start)) {
                map.put(start, new ArrayList<>());
            }
            map.get(start).add(end);
        }
        
        // 알파벳 순으로 정렬
        for(List<String> list : map.values()) {
            Collections.sort(list);
        }
        
        dfs("ICN");
        return answer.toArray(new String[0]);
    }
    
    static void dfs(String start) {
        answer.add(start);
        
        if(answer.size() == totalTickets) {
            isComplete = true;
            return;
        }
        
        // 현재 갈 수 있는 도착지 리스트
        List<String> endList = map.get(start);
        
        // 해당 시작지점에서 도착지가 없거나, 모든 도착지를 방문한 경우
        if(endList == null || endList.isEmpty()) {
            // 현재 공항 제거
            answer.remove(answer.size() - 1);
            return;
        }
        
        // 가능한 도착지 탐색
        for(int i=0; i<endList.size(); i++) {
            // 현재 도착지 선택
            String next = endList.remove(i);
            dfs(next);
            
            // 경로 다 찾았으면 더 이상 탐색하지 않음
            if (isComplete) return;

            // 도착지 원상복구
            endList.add(i, next);
        }
        
        answer.remove(answer.size() - 1);
    }
}

 

[풀이 과정]

1. 출발지와 도착지를 Map에 저장한다.

2. answer이라는 ArrayList를 선언하여, Dfs시 결과를 저장한다.

3. 만약, dfs에서 해당하는 도착지가 출발 지점으로 바뀌어 다시 Dfs를 돌 때, 해당 지점의 도착지가 존재하지 않는 경우, 이전 방향에서 다른 도착지로 향해야 하므로 Dfs에서 answer에 저장한 마지막 값을 없앤 다음 리턴해준다.

4. 정확한 경로를 찾았을 때는 Return을 하여 재귀를 종료하여야 하는데, 그렇지 않은 경우에는 마지막에 저장한 answer값의 도착지를 제거해줘야 하므로, 마지막에 answer.remove(answer.size()-1);을 수행해준다.

 

1,2번 테스트케이스에서 반례가 발생했었다. 동일하게 문제를 틀리는 사람은 아래 반례를 추가해보면 확인 가능하다.
[["ICN", "BBB"], ["BBB", "ICN"], ["ICN", "AAA"]] => ["ICN", "BBB", "ICN", "AAA"]

 

풀이 시간 : 2시간