알고리즘) 프로그래머스 Level 3 여행경로 Swift

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

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

---

예제

입력	출력
[["ICN", "JFK"], ["HND", "IAD"], ["JFK", "HND"]]	["ICN", "JFK", "HND", "IAD"]
[["ICN", "SFO"], ["ICN", "ATL"], ["SFO", "ATL"], ["ATL", "ICN"], ["ATL","SFO"]]	["ICN", "ATL", "ICN", "SFO", "ATL", "SFO"]
[["ICN", "B"], ["B", "ICN"], ["ICN", "A"], ["A", "D"], ["D", "A"]]	["ICN", "B", "ICN", "A", "D", "A"]

 

---

문제 접근

경로를 찾아가는 문제로 DFS를 이용해 문제를 풀 수 있습니다.

1. 우선 모든 티켓을 정렬합니다.
2. 방문 여부를 알 수 있는 Bool 배열을 생성합니다.
3. 재귀함수를 사용해 도착지를 다음 출발지로 호출합니다.
4. 모든 도시를 방문했으면 종료하여 재귀함수를 탈출합니다.

 "모든 도시를 방문할 수 없는 경우는 주어지지 않습니다." 조건이 붙어 있으므로,
현재 경로가 모든 도시를 방문할 수 없을 경우 취소하고 다른 도시를 방문하도록 해야 합니다.
그래서 공항 경로 개수와 티켓 개수 +1 와 같지 않으면 공항 경로에서 제거하고 방문하지 않았다고 원복해야 합니다.

💡 공항 경로 개수와 티켓 개수 +1을 비교하는 이유는 티켓이 3개라면 4곳을 방문하기 때문입니다.

 

풀이