[프로그래머스#JS] 여행 경로
문제
https://programmers.co.kr/learn/courses/30/lessons/43164
풀이
- 처음부터 정렬하면 index 순으로 돌기 때문에 자동으로 알파벳 순으로 여행 경로가 설정됩니다.
- 시작을 'ICN'으로 두고 DFS.
모든 도시를 방문할 수 없는 경우는 주어지지 않습니다.
이 한마디 때문에 엄청 헤맸습니다. 최종 정답이 모든 도시를 방문할 수 있다는 얘기지, 아무렇게나 가도 모든 도시를 방문할 수 있다는 말이 아닙니다. 아래의 테스트 케이스로 DFS를 딱 한 번만 돌리면 모든 도시를 방문할 수 없습니다.
const tickets = [
['ICN', 'COO'],
['ICN', 'BOO'],
['COO', 'ICN'],
['BOO', 'DOO'],
];
- path의 길이가 tickets 길이의 +1 일 때, 모든 도시를 방문할 수 있는 path고, 가능한 길을
answer
배열에 모두 넣습니다. 처음에 정렬을 했기 때문에answer[0]
이 정답이 됩니다.
코드
function solution(tickets) {
tickets = tickets.sort();
let isVisited = new Array(tickets.length).fill(false);
let path = ['ICN'];
let answer = [];
function DFS(FROM) {
if (path.length === tickets.length + 1) {
answer.push([...path]);
return;
}
tickets.forEach(([from, to], i) => {
if (from === FROM && !isVisited[i]) {
isVisited[i] = true;
path.push(to);
DFS(to);
isVisited[i] = false;
path.pop(to);
}
});
}
DFS('ICN');
return answer[0];
}
Author And Source
이 문제에 관하여([프로그래머스#JS] 여행 경로), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@tunakim/프로그래머스JS-여행-경로저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)