[프로그래머스] 여행경로 문제 자바스크립트 풀이

> 문제 바로가기

코딩테스트 연습 - 여행경로

 

 

1. 접근 방법

 

- [["ICN", "JFK"], ["HND", "IAD"], ["JFK", "HND"]] 이런 그래프고 각 노드의 [0]이 출발, [1]이 도착임

- 문제에서 항상 ICN 공항에서 출발한다고 했으므로 출발지는 'ICN'

- 주어진 tickets(array), 시작노드 'ICN'(string), 탐색중인 경로 path(array), 결과 담을 routes(array)

 

(1) 만약 tickets가 비어 있으면 모든 노드를 다 돌았다는 의미이므로 [...path, next]를 routes에 넣음.

(2) 그렇지 않으면 재귀로 next의 다음 노드를 path에 넣어줌.

 

2. 풀이

const findPath = (tickets, routes, next, path) => { 
    if (tickets.length === 0) {
        routes.push([...path, next]);
        return;
    }
    
    const nextNodes = tickets.filter(ticket => ticket[0] === next);
    nextNodes.forEach((nextNode, idx) => {
        const newTickets = tickets.filter(ticket => ticket !== nextNode);
        findPath(newTickets, routes, nextNode[1], [...path, next]);
    })
}

function solution(tickets) { 
    let routes = [];    
    findPath(tickets, routes, 'ICN', []); 
    return routes.sort()[0];
}