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

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

 

문제 설명

 

주어진 항공권을 모두 이용하여 여행경로를 짜려고 합니다. 항상 "ICN" 공항에서 출발합니다.

항공권 정보가 담긴 2차원 배열 tickets가 매개변수로 주어질 때, 방문하는 공항 경로를 배열에 담아 return 하도록 solution 함수를 작성해주세요.

제한사항

• 모든 공항은 알파벳 대문자 3글자로 이루어집니다.
• 주어진 공항 수는 3개 이상 10,000개 이하입니다.
• tickets의 각 행 [a, b]는 a 공항에서 b 공항으로 가는 항공권이 있다는 의미입니다.
• 주어진 항공권은 모두 사용해야 합니다.
• 만일 가능한 경로가 2개 이상일 경우 알파벳 순서가 앞서는 경로를 return 합니다.
• 모든 도시를 방문할 수 없는 경우는 주어지지 않습니다.

입출력 예

 

tickets

return

[["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"]

입출력 예 설명

예제 #1

["ICN", "JFK", "HND", "IAD"] 순으로 방문할 수 있습니다.

예제 #2

["ICN", "SFO", "ATL", "ICN", "ATL", "SFO"] 순으로 방문할 수도 있지만 ["ICN", "ATL", "ICN", "SFO", "ATL", "SFO"] 가 알파벳 순으로 앞섭니다.

 

dfs문제

 

맨 처음에 짠 코드

이는 초기에 짠 코드이다.

문제점 1) 정렬을 한다면 굳이 불필요한 변수를 만들어 저장하고 또 비교하고 할 필요가 없다.

-> 그래서 solution부분에서 정렬을 해주고 dfs를 들어갔다.

문제점 2) 정확도 테스트 1,2번에서 자꾸 실패가 떴다.

-> 인터넷에 검색한 결과,

• 입력 : [[ICN, A], [ICN, B], [B, ICN]]
• 답 : [ICN, B, ICN, A]

이렇게 주어지는 경우 ICN->A->??? 이렇게 되어서 답이 구해질 수 없다.

(문제 조건에 모든 도시를 방문할 수 없는 경우는 존재하지 않는다고 했기 때문)

이 예제를 본 후에야 경우의 수가 한 가지가 아니라 여러 가지가 나올 수 있다는 사실을 알았고,

왜 사람들이 for문 안에 dfs를 넣어주고 dfs를 빠져나온 후 check배열을 false로 다시 바꿔주었는지 알 수 있었다.

(경로 찾기에 실패한 경우 빠져나와서 그 경우를 삭제시켜주어야 하기 때문)

 

*return true와 false는 결과에 영향을 미치지 않는다. true부분을 false로 false 부분을 true로 바꿔줘도 된다는 말.

그냥 직관적으로 성공과 실패를 알아볼 수 있게 쓴 것이다.