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

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

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

# 프로그래머스 여행경로

def solution(tickets):
    global answer
    answer = []
    fromto = {}
    manage_ticket = {}
    temp = []
    for ticket in tickets:
        dep, arr = ticket
        manage_ticket[dep+arr] = 0
        fromto[dep] = []
        fromto[arr] = []
    for ticket in tickets:
        dep, arr = ticket
        fromto[dep].append(arr)
        manage_ticket[dep+arr] += 1
    for dep in fromto.keys():
        fromto[dep].sort()
    print(fromto)

    def dfs(dep):
        global answer
        if len(temp) == len(tickets)+1:
            if not answer:
                answer = list(map(str, temp))
        else:
            if fromto[dep]:
                for arr in fromto[dep]:
                    if manage_ticket[dep+arr] >= 1:
                        temp.append(arr)
                        manage_ticket[dep+arr] -= 1
                        dfs(arr)
                        temp.pop()
                        manage_ticket[dep+arr] += 1
    temp.append("ICN")
    dfs("ICN")
    return answer

DFS 문제이다. 딕셔너리를 이용해서 출발지를 key 값으로, 도착지를 values로 정하고, 도착지의 values 값을 정렬하였다.

그 후에, DFS를 실행해주면 된다.

 

프로그래머스에 4개의 테스트 케이스가 존재하는데, 1번 2번이 통과가 되지않았다.

이유는 다음과 같았다.

 

1. 모든 출발지와 도착지에 대해 fromto 딕셔너리에 [](리스트)를 만들어야 했다.

2. 반복되는 이동에 대한 고려 ( EX 인천-하네다, 하네다-인천, 인천-하네다, 하네다-인천, 인천-하네다)를 해줘야 했다.