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

최종 코드

import sys
from collections import deque
input = sys.stdin.readline
tickets=[list(map(str,input().strip().split(" "))) for _ in range(5)]

# #BFS
# answer=[]
# q=deque()
# q.append(("ICN",["ICN"],[]))
#
# while q:
#     airport,path,used=q.popleft()
#
#     if len(used)==len(tickets):
#         answer.append(path)
#
#     for idx,ticket in enumerate(tickets):
#         if ticket[0] == airport and not idx in used:
#             q.append((ticket[1],path+[ticket[1]],used+[idx]))
#
# answer.sort()
# print(answer[0])

#DFS
visited = [False]*(len(tickets))
answer=[]

def dfs(airport,path):
    if len(path) == len(tickets)+1:
        answer.append(path)
        return

    for idx, ticket in enumerate(tickets) :
        if ticket[0]==airport and visited[idx]==False :
            visited[idx]=True
            dfs(ticket[1],path+[ticket[1]])
            visited[idx]=False

dfs("ICN",["ICN"])
answer.sort()

print(answer[0])

 

설명

BFS와 DFS 두가지 방법으로 풀이 가능.

BFS

• airport 는 출발 공항, path는 경로, used는 사용한 티켓의 index
• 제일 먼저 ICN에서 출발해야하므로 q에 airport ="ICN" path=["ICN"] used=[]을 넣어준다.
• 그 이후 q에 인자가 있는동안 while문을 진행한다.
• while문 안에서 ticket리스트에 대하여 enumerate로 반복문을 돌린다.
• ticket[0]와 airport가 같고 그 ticket이 사용되지 않은 티켓이라면, used에 ticket의 index를 넣어주고. path에 해당 ticket의 도착지를 넣어주고, 출발 공항을 ticket의 도착지로 바꾸어서 q에 append한다.
• used의 길이와 tickets의 길이가 같아지면 answer리스트에 append한다.
• 반복문이 끝나면 answer을 sort하고 answer[0]을 출력한다. 

DFS

• ticket리스트 길이만큼의 visited리스트를 만든다.
• 이 또한 출발 공항이 ICN이므로 airport에 "ICN" path에 ["ICN"]으로 시작한다.
• tickets을 enumerate로 반복문을 진행하는데, ticket[0]와 airport가 같고 visited[i]가 false이면, visited[i]를 True로 바꾸고 dfs함수를 재귀적으로 호출한다. 이때 airport는 ticket[1] path는 path+ticket[1]이다.
• dfs를 호출하고 visited[i]를 False로 다시 돌려준다. - 다른 가능한 경로를 탐색할 때 티켓을 다시 사용할 수 있도록 하기 위함이다. (백트래킹)
• path의 길이와 tickets의 길이 +1 이 같으면 path를 answer 에 append한다.
• dfs가 끝나면 answer을 sort하고 answer[0]을 출력한다.