[DFS/BFS] 여행경로

프로그래머스 Level 3

 

 

처음 설계한 코드는 tickets을 먼저 sort하여 알파벳 순으로 정렬한 후 이리저리 코드를 짰는데

입출력 예의 사례에서는 통과가 되었지만 정답 채점에서 테스트 1, 2를 통과 못했다.

도대체 왜일까 찾아보다

 

tickets
[["ICN", "A"], ["A", "B"], ["A", "C"], ["C", "A"], ["B", "D"]]

return
["ICN", "A", "C", "A", "B", "D"]

 

사례를 보았다!

 

이 사례를 바탕으로 요리조리 하다보니 최종적으로 아래와 같은 코드로 작성하였다!

def dfs(curAirport, tickets, result):
    result.append(curAirport)
    canAirport = []
    for i in tickets:
        if i[0] == curAirport:
            canAirport.append(i[1])
    canAirport.sort()
    if len(canAirport) == 0 and len(tickets) == 0:
        return result
    for j in canAirport:
        if len(tickets) == 0:
            break
        index = tickets.index([curAirport, j])
        tickets.remove([curAirport, j])
        dfs(j, tickets, result)
        if len(tickets) == 0: return result
        result.pop()
        tickets.insert(index, [curAirport, j])
def solution(tickets):
    result = []
    return dfs("ICN", tickets, result)

 

하루종~일 풀었다 하핫 처음 풀었을 때는 로직 자체를 잘못 설계했고 이후에는 머릿속으로 설계한 로직을 파이썬으로 구현하는데 생각보다 시간을 많이 쏟았다 dfs의 정석(?)대로 문제를 풀지는 않았지만 어쨌든 ,, 성공!