[ProblemSolving] 프로그래머스 - 여행경로(dfs&bfs) [Level3]

문제 링크

문제 설명

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

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

제한 사항

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

입출력 예

예제 #1

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

예제 #2

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

잘못된 초기 풀이와 코드

통과하지 못하는 테스트 케이스가 있다.

덕봇기님 반례를 참고했다.

[ ['ICN', 'A'], ['A', 'B'], ['A', 'C'], ['C', 'A'], ['B', 'D'] ]

문제에서, 오름차순으로 길을 선택하라고 했지만, B를 먼저 가게 되면 답이 될 수 없다.

따라서, ICN -> A -> B -> D의 경로에서, D까지 갔다가 A로 돌아올 수 있어야 한다.

# 잘못된 코드
else:
	return stack

# 수정한 코드    
else:
  	answer.append(stack.pop())	   

answer에 D를 저장하고, D가 끊어지면, B도 끊어지며, answer에 B를 저장한다.

A는 C가 남아있기 때문에 다시 진행하여 A -> C -> A -> B(X) -> D(X) 이므로, A를 다시 answer에 저장하고, 나머지 C,A도 저장한다.

answer = ['D', 'B', 'A', 'C', 'A', 'ICN'], 이것을 뒤집어서 출력해주면 답이 된다.

def solution(tickets):
    routes = {}
    for t in tickets:
        routes[t[0]] = routes.get(t[0],[]) + [t[1]] 
    for r in routes:
        routes[r].sort(reverse=True) 
    stack = []
    stack.append("ICN")
    
    while stack:
        top = stack[-1] # 상단
        if top in routes and routes[top]:
            stack.append(routes[top].pop())
        else:
            return stack
        

수정한 나의 풀이와 코드

routes는 출발지:[도착지1, 도착지2] 딕셔너리로 key, value를 설정한다.
routes : {'ICN': ['SFO', 'ATL'], 'SFO': ['ATL'], 'ATL': ['SFO', 'ICN']}

도착지를 오름차순으로 선택하기 때문에, values값들을 내림차순으로 정렬하여,
stack의 상단에서 사전순으로 도착지를 꺼낸다.

현재 출발지(top)에서 갈 수 있는 도착지가 있다면, 사전순으로 도착지를 꺼내서 stack에 저장해준다.

꺼낸 도착지가 routes에 존재하지 않을때, 현재 출발지를 pop해서 넣어 준다.

def solution(tickets):
    routes = {}
    for t in tickets:
        routes[t[0]] = routes.get(t[0],[]) + [t[1]] 
    for r in routes:
        routes[r].sort(reverse=True) 
    stack = []
    stack.append("ICN")
    
    while stack:
        top = stack[-1] # 상단
        if top in routes and len(routes[top])!=0:
            stack.append(routes[top].pop())
        else:
            answer.append(stack.pop())
    answer.reverse()
    return answer

feedback

딕셔너리 변환 부분, 스택에서 사전순으로 꺼내기 위해 정렬하는 부분, 예외 케이스 등
고려해야할 부분이 많았고, 어려웠다. 연습이 많이 필요한 문제였다.