[Basic_Algorithm] [BFS/DFS] #2

DFS로 풀어야 하는 문제 같은데, 처음 접근하는데 있어서 DFS로 접근하지 못하였다. 시행착오에 대해서 기록해두려고 한다. 

먼저 문제는 다음과 같았다. (출처; https://programmers.co.kr/ 프로그래머스 > 코딩테스트 연습 > 깊이/너비 우선탐색 > 네트워크)

""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""
주어진 항공권을 모두 이용하여 여행경로를 짜려고 합니다. 항상 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. 첫번째 시도, dic() 과 heapq()을 사용하여, 출발지를 key로 담고 이에 해당하는 도착지를 value값으로 가지되, 이를 heapq형태로 저장하였다. 왜냐하면, "만일 가능한 경로가 2개 이상일 경우 알파벳 순서가 앞서는 경로를 return 합니다."라는 조건이 주어졌기 때문이다. 그러나, runtime error가 걸렸다. 효율적인 코드는 아니었나보다.

 

2. 두번째 시도, DFS아이디어에 기반하여 재귀적으로 해결하려고 한 경우다. 모든 항공지를 경유하게 되면 input으로 받게 되는 배열리스트의 길이보다 1보다 큰 곳을 최종적으로 방문하게 된다. 재귀함수 부분에서는 방문한 장소의 길이가 N+1인 경우, return하게 하는 부분이 base이다. 그렇게 dictionary형태에 d['출발지'] = 도착지를 담은 리스트을 넣고, 방문한 장소들은 ["ICN"]에서부터 시작하여 temp에 차곡차곡 쌓이게 한다. "ICN"에서 출발하여 각각 도착하는 장소에 대해서 다시 recursive의 input key로 들어가는 구조다. 출발지 "ICN"로부터 시작하여 알파벳 order 높은 순위로 DFS로 탐색하였다. 

그 외 메모 : 출처(https://dongdongfather.tistory.com/69)

defaultdict()는 딕셔너리를 만드는 dict클래스의 서브클래스이다.

작동하는 방식은 거의 동일한데, defaultdict()는 인자로 주어진 객체(default-factory)의 기본값을 딕셔너리값의 초깃값으로 지정할 수 있다.

숫자, 리스트, 셋등으로 초기화 할 수 있기 때문에 여러 용도로 사용할 수 있다.