코테/프로그래머스
프로그래머스 level3 [여행경로] 파이썬
동 캄
2022. 4. 8. 16:14
반응형
https://programmers.co.kr/learn/courses/30/lessons/43164
코딩테스트 연습 - 여행경로
[["ICN", "SFO"], ["ICN", "ATL"], ["SFO", "ATL"], ["ATL", "ICN"], ["ATL","SFO"]] ["ICN", "ATL", "ICN", "SFO", "ATL", "SFO"]
programmers.co.kr
# 프로그래머스 여행경로
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 인천-하네다, 하네다-인천, 인천-하네다, 하네다-인천, 인천-하네다)를 해줘야 했다.
반응형