서문
오늘은 프로그래머스에서 "여행경로"라는 문제를 풀어보았다. 이 문제는 분류상 DFS/BFS에 속하는 문제다. 지금은 문제를 풀 때, 이 문제가 어떤 알고리즘으로 풀어야 하는 문제인지 알 수 있지만 고득점 kit을 다 풀고나서는 최대한 모르는 상태에서 진행해야겠다. 확실히 어떤 알고리즘을 사용해야하는지 아는것부터 엄청난 힌트라고 생각이 되기 때문이다.
그리고 역시 또 DFS로 풀고 말았다. BFS로 푸는 것도 연습해야 하는데 이번 주말에 꼭 진행해야 겠다.
소스 코드
function solution(tickets) {
let answer = 0;
const routeList = []; // 가능한 모든 경로를 저장할 리스트
travel(['ICN'], [], 0); // 처음 출발은 무조건 ICN이다.
// 가능한 모든 경로 중에서 알파벳 순으로 정렬했을 때, 첫 번째가 정답
answer = routeList.sort((a, b) => {
for (let i = 1; i < a.length; i++) {
if (a[i] === b[i]) continue;
// 공항이 같으면 다음 공항을 비교해야 한다
else {
if (a[i] < b[i]) return -1;
else if (a[i] > b[i]) return 1;
}
}
return 0;
})[0];
return answer;
function travel(route, usedTicketIndex, cnt) {
// 종료 조건: 모든 티켓을 다 쓴 그 순간이 종료되야하는 시점
if (cnt === tickets.length) {
routeList.push(route);
return;
}
// 티켓들을 쭉 보면서
for (let i = 0; i < tickets.length; i++) {
// 쓴 티켓은 제외하고
if (usedTicketIndex.includes(i)) continue;
// 현재 있는 곳에서 갈 수 있는 모든 공항을 travel 해준다.
if (tickets[i][0] === route[route.length - 1]) {
travel([...route, tickets[i][1]], [...usedTicketIndex, i], cnt + 1);
}
}
return;
}
}풀이 설명
변수 목록
- answer - 정답을 저장할 변수
- routeList - 가능한 모든 경로를 저장하는 배열
재귀함수를 돌면서 routeList에 모든 여행가능한 경로를 저장할 것이다.
function travel
처음에 이 함수를 구현할 때 어떤 것들을 매개변수로 넘기면서 가지고 다닐 지 고민했다. 하나의 티켓을 갖고 다닐지, 아니면 현재 목적지만 갖고 다닐지 고민하다가 현재까지의 경로를 갖고 다니는게 나한테 제일 편하다고 판단했다. 사실 어떤 것을 가지고 다니든 본인이 편한대로 구현해서 성공하기만 하면 된다.
매개변수 설명
- route - 여행을 다니면서 현재까지 도착한 경로들을 가지고있는 배열
- usedTicketIndex - 사용한 티켓들의 인덱스 값을 저장하는 배열
- cnt - 여행 횟수
먼저 탈출조건으로 여행 횟수가 티켓의 갯수랑 같아지면 return하게끔 설정했다.
그리고 그 때까지 여행다니면서 만들어진 route를 routeList에 저장하도록 했다.
그 다음 현재 route의 마지막을 기준으로 갈 수 있는 여행지를 몰색했다. 갈 수 있으면 무조건 다시 travel()함수를 재귀적으로 호출해준다. 이렇게 되면 탈출조건에 걸리기 전까지 갈 수 있는 다음 목적지로 계속해서 가게된다.
그 다음 travel함수가 다 종료되게 되면 routeList에는 갈 수 있는 모든 여행경로가 담기게 되는데, 이 중에서 알파벳 순으로 제일 앞에 오는 경로를 answer에 넣어 반환해주면 된다.
후기
어제 같은 유형의 문제를 풀어서 그런지 비교적 빠른 시간내에 풀린 것 같다. 내일부터는 새로운 유형의 알고리즘 문제를 풀 생각인데 오늘처럼 순조롭게 풀렸으면 좋겠다.
