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

     

목차

 

문제

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

프로그래머스

 

 

문제 구현 방향

1. 인접 리스트를 만든다.

2. 이때 방문처리를 위한 배열을 따로 만들지 말고 인접 리스트에 넣는 것이 훨씬 더 풀기가 쉽다. (그래야 idx를 따로 처리하는 귀찮음이 발생하지 않음)

3. 답이 구해지면 바로 끝낼 수 있도록 플래그를 외부에 선언한다.

 

 

코드 구현

function solution(tickets) {
    let answer = [];
    
    // 1. 알파벳 순으로 미리 정렬 (그래야 첫 정답이 무조건 답이 됩니다)
    tickets.sort();
    
    // 2. 인접 리스트(Map/Object 형태) 생성
    let adjList = {};
    for (let [from, to] of tickets) {
        if (!adjList[from]) adjList[from] = [];
        adjList[from].push({ to: to, isUsed: false }); // 방문 여부를 티켓별로 붙임
    }
    
    let path = ['ICN'];
    const totalTickets = tickets.length;
    let isFinished = false;

    function dfs(curNode, count) {
        // 모든 티켓을 다 썼다면 정답 저장 후 즉시 탈출 신호(true) 송신
        if(isFinished) return;
        if (count === totalTickets) {
            answer = [...path];
            isFinished = true;
        }
        
        // 현재 공항에서 출발하는 티켓 리스트를 인접 리스트에서 바로 가져옴
        let nextTickets = adjList[curNode];
        if (!nextTickets) return false; // 더 갈 곳이 없으면 실패
        
        for (let ticket of nextTickets) {
            if (ticket.isUsed) continue; // 이미 쓴 티켓이면 패스
            
            ticket.isUsed = true; // 티켓 사용 처리
            path.push(ticket.to);
            
            // 다음 공항으로 넘어가서 성공(true)을 반환받으면 연쇄 종료
            dfs(ticket.to, count + 1)
            
            ticket.isUsed = false; // 원상 복구 (백트래킹)
            path.pop();
        }

    }
    
    // 항상 "ICN" 공항에서 시작, 사용한 티켓 수는 0장부터 시작
    dfs('ICN', 0);
    
    return answer;
}