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

문제 링크: https://programmers.co.kr/learn/courses/30/lessons/43164

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

 

여러 공항이 있고, 출발지와 도착지가 적힌 티켓이 tickets 배열에 주어집니다.

Tickets 내의 모든 티켓들을 각각 한 번씩만 사용하여, 주어진 모든 도시를 방문하는 경우의 방문 순서를 구하는 문제입니다.

모든 도시를 방문할 수 없는 경우는 입력으로 주어지지 않으며, 가능한 경우가 여러 가지 존재하는 경우, 알파벳 순으로 가장 앞서는 하나의 경우를 답으로 return합니다.

 

DFS (깊이 우선 탐색)을 통해 접근하였습니다.

구현의 편리함을 위해 재귀함수를 이용하였고, 매 방문 시마다 사용한 티켓을 체크하고, 방문한 경로에 추가한 후, 다음 함수에 넘기는 방법으로 접근하였습니다.

방문한 도시의 숫자는 티켓의 수 + 1이어야 하므로, 접근할 수 있는 도시가 없고 방문한 도시의 숫자가 조건을 만족하는 경우 answer_candidates 배열에 추가합니다.

탐색을 마친 후, 가능한 경로가 여러 개 존재할 경우, 이를 문제의 조건에 맞게 정렬합니다. 정렬을 위해 ans_sort 함수를 별도로 작성하였습니다.

이후 answer_candidates의 맨 앞 원소를 답으로 return하면 됩니다.

 

채점 결과

테스트 케이스가 달랑 4개라서... 잘 풀었는지 모르겠네요.

DFS를 이용하는 적당한 난이도의 문제였던 것 같습니다.