[Python] 03-03 여행경로

문제 설명

주어진 항공권을 모두 이용하여 항상 "ICN" 공항에서 출발하도록 여행경로

항공권 정보가 담긴 2차원 배열 tickets가 매개변수로 주어질 때, 방문하는 공항 경로를 배열에 담아 return

 

제한사항

모든 공항은 알파벳 대문자 3글자로 이루어집니다.

주어진 공항 수는 3개 이상 10,000개 이하입니다.

tickets의 각 행 [a, b]는 a 공항에서 b 공항으로 가는 항공권이 있다는 의미입니다.

주어진 항공권은 모두 사용해야 합니다.

만일 가능한 경로가 2개 이상일 경우 알파벳 순서가 앞서는 경로를 return 합니다.

모든 도시를 방문할 수 없는 경우는 주어지지 않습니다.

---

내 풀이

def solution(tickets):      # 항공권
    answer = []             # 방문하는 공항 경로    
    stack = []              # 도착지 공항 
    visited = [False] * len(tickets)
    
    tickets.sort(key=lambda x:x[1])     # 도착지 순으로 경로 정렬
    
    # 첫 출발지는 ICN
    start = 'ICN'
    stack.append(start)
    answer.append(start)
        
    while stack:
        next = None
        
        for i, ticket in enumerate(tickets):    # 알파벳 순 접근 (앞서 정렬함)
            if ticket[0] == start and not visited[i]:  
                next = ticket[1]
                break 
        
        if next != None :   # 다음에 방문할 곳 있으면
            start = next            
            answer.append(start)            # 방문기록
            stack.append(ticket[1])         # 도착지를 stack에 담기
            visited[i] = True               # 항공권 사용 처리
        else:
            start = stack.pop()     # 다음 경로가 없으면 되돌아가기
    
    return answer

- 테스트 케이스는 통과를 하는데 테스트1, 2에서 계속 실패한다

- 테스트 케이스 세우는 법도 연습이 필요하다

---

풀이

DFS 알고리즘 적용이 필요한 문제이다. 한붓그리기를 해야함

- 한붓그리기가 가능함은 문제에서 보장하고 있음

- 시작 정점은 언제나 'ICN'

- 모든 정점 방문 X, 모든 간선을 거쳐야함

- 한 정점에서 택할 수 있는 간선이 두개 이상이면 > 알파벳 순서를 따름

 

✔ 스택을 사용하자! (재귀적인 성질)

1. 방문하는 공항을 스택에 넣기

2. 더이상 갈곳이 없는 경우 > 스택에서 꺼내서 temp에 기록

3. ICN으로 돌아와서 재 출발 

4. 모든 공항을 방문하여 티켓이 남아있지 않은 경우 스택에서 다 꺼내기 

5. 꺼낸 공항들은 방문순서 역순임 > 반대로 정렬 필요

 

그래프의 표현

딕셔너리 이용 - 각 공항에서 출발하는 항공권의 리스트(알파벳 순서가 필요하기 때문)을 표현

{'ICN' : ['ATL', 'SFO'], 'ATL' : ['ICN', 'SFO'] } > 알파벳 역순으로 정렬

> {'ICN' : ['SFO', 'ATL'], 'ATL' : ['SFO', 'ICN' ] } 

 

바람직한 코드 ^^

def solution(tickets):
	routes = {}
    
    for t in tickets:
    	routes[t[0]] = routes.get(t[0], []) + t[1]		# 리스트 형태의 Value(도착지) 추가
    
    for r in routes:
    	routes[r].sort(reverse=True)	# 도착지를 알파벳 역순으로 정렬 : O(NlogN)
    
    stack = ["ICN"]		# 방문한 경로 기록 - 출발지 삽입
    path = []			# 경로를 기록할 리스트
    
    while len(stack) > 0:		# 표 갯수 만큼 반복 : O(N)
    	top = stack[-1]			# 가장 마지막으로 도착한 도착지
        
        if top not in routes or len(routes[top]) == 0:	# 마지막 방문지에서 갈 경로가 없으면
        	path.append(stack.pop())			# 방문 처리
        else:	
        	stack.append(routes[top][-1])		# top에서 방문할 수 있는 공항 중 알파벳 순 우선인 공항 방문
            routes[top] = routes[top][:-1]		# 방문한 공항의 티켓 제거
            
    return path[::-1]		# 역순 리턴