728x90
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
분석
무조건 알파벳 순서가 앞서는 곳을 향하도록 여행 경로를 구성하면 문제의 답을 올바르게 구할 수 있음을 보장하지 않음
ticket result [["ICN", "AAA"], ["ICN", "CCC"], ["CCC", "DDD"], ["AAA", "BBB"], ["AAA", "BBB"], ["DDD", "ICN"], ["BBB", "AAA"]] ["ICN", "CCC", "DDD", "ICN", "AAA", "BBB", "AAA", "BBB"] 위 예시에서 처음에 "ICN"에서 출발하여 "AAA"를 먼저 방문한다면 주어진 항공권을 모두 사용하지 못합니다.
대신에 "CCC"를 먼저 방문한다면 항공권을 모두 사용하는 경로를 구성할 수 있습니다.
풀이
def solution(tickets):
answer = []
n=len(tickets)
visited=[False]*len(tickets)
def dfs(v, path):
if len(path) == n+1:
answer.append(path)
return
for i,ticket in enumerate(tickets):
s,e=ticket
if v==s and not visited[i]:
visited[i] = True
dfs(e, path+[e])
visited[i] = False
dfs("ICN",["ICN"])
answer.sort()
return answer[0]
728x90