[프로그래머스] 여행 경로(Python) (실패)

프로그래머스 - 여행 경로

풀이

1. 티켓이 연결되어야 하므로 dfs 사용

2. 알파벳 순으로 도착지를 정함 -> 도착지 기준 정렬
   -> list.sort(key=lambda x:x[1])

3. dfs

• 파라미터 start : 출발지
• visited -> 간선의 개수만큼, 간선 방문 정보 표시
• answer의 길이 = 간선의 개수 + 1 이기 때문에 충족되면 dfs 종료

문제점

한 곳에서 다른 곳으로 가는 간선이 여러개인 경우 반례 존재

tickets = [["ICN", "BOO"], ["ICN", "COO"], ["COO", "DOO"], ["DOO", "COO"], ["BOO", "DOO"], ["DOO", "BOO"], ["BOO", "ICN"], ["COO", "BOO"]]
answer = ["ICN", "BOO", "DOO", "BOO", "ICN", "COO", "DOO", "COO", "BOO"]
output = ['ICN', 'BOO', 'DOO', 'BOO', 'ICN', 'COO', 'BOO', 'DOO', 'COO'] #fail

백트래킹해서 뒤로갈 때 기존 answer에서 pop하고 새로 넣고싶은데... 어떻게 하는지 도저히 모르겠다.....

코드(실패)

def solution(tickets):
	answer = ['ICN']
	visited = [0] * len(tickets)

	def dfs(start):
		for i, ticket in enumerate(tickets):
			if len(answer) == len(tickets) + 1:
				return 0
			if ticket[0] == start and not visited[i]:
				visited[i] = 1
				answer.append(ticket[1])
				dfs(ticket[1])

	tickets.sort(key=lambda x:x[1])
	dfs('ICN')
	return answer