https://programmers.co.kr/learn/courses/30/lessons/43164
DFS를 파이썬에서 어떤식으로 활용하는지에 대해서 이해도가 부족하다 보니,
리스트를 자르는 과정에서 계속해서 해매는 상황이 발생했다. 이번에는 45점을
바쳐서 한번 좋은 풀이과정을 참조해 보고, 코드 리뷰를 한 뒤에 직접 이를
활용하고자 한다.
테스트 케이스 1번 2번이 안된다구?
프로그래머스 특성상, 테스트케이스에 대한 정보를 알려주지 않기 때문에, 풀이나 블로그글에서 테스트케이스 정보를 찾아야 하는 경우가 많다.
요약하자면, DFS로 재귀적인 색인을 하지만, 여행티켓을 모두 쓰지 않는 경우가 생긴다.
tickets리스트
[["ICN", "COO"], ["ICN", "BOO"], ["COO", "ICN"], ["BOO", "DOO"]]
return값
["ICN", "COO", "ICN", "BOO", "DOO"]
아래 코드에서 나는 처음에 왜 한 key값의 enumerate에서 loop를 도는지 이유를 몰랐었는데, 이유가 있었다. 그렇기에 한 처리되어진 값이 깊이 단계에 따라서 순회를 하면서 퍼져나가며, 조건에 맞는 이상적인 방향을 찾도록 해주는 처리를 위해, 사용한 key의 country값을 pop하고, 재귀dfs를 실행 후 다시 넣어주는 것이다.
"티켓을 다 사용하지 못하고 DFS가 끝나는 경우가 있다."
이상황이 된다면 ICN -> BOO -> DOO 끝. 이렇게 되어버린다.
그렇기 때문에 ICN의 다음선택지로 초기시작점에서 다른 DFS방향을 타주는 것에 대한 설정이 필요하다.
풀이과정
##1.DFS의 자료구조적 성격을 잘 처리하려면 deque와 관련되어진 라이브러리를 많이 활요한다.
"""
graph : dict형으로 바꾼 defaultlist형
N : 티켓의 길이
key : "ICN" 출발하는 공항의 지점
footprint : ["ICN"] 배열 "ICN"이 들어있는 ARRAY
"""
from collections import defaultdict
##2.DFS함수의 구현
def dfs(graph, N, key, footprint):
print(footprint)
#footprint의 배열 길이가 요청한 배열길이보다 많다면 footprint를 반환한다
#작업이 끝났다는 뜻
if len(footprint) == N + 1:
return footprint
#특정 dict에 대한 key에 대한 value list의 idx, country에서
for idx, country in enumerate(graph[key]):
graph[key].pop(idx) #idx에 대한 값을 pop처리하고
print("footprint:", footprint)
tmp = footprint[:] #리스트전체를 복사헤서 tmp에 가져옴(footprint를 써도 상관없으나, 리스트 전체를 복사해서 붙여넣기 한다는 의미로 사용한 것으로 보임
print("tmp:", tmp)
tmp.append(country)
ret = dfs(graph, N, country, tmp)
graph[key].insert(idx, country)
if ret:
return ret
def solution(tickets):
answer = []
graph = defaultdict(list)
print(list)
print(graph)
N = len(tickets)
for ticket in tickets:
graph[ticket[0]].append(ticket[1]) #ticket에서 배열의 0번째 인덱스 값이 key, 1번째 인덱스값이 valu로 들어감
graph[ticket[0]].sort() #누적되어지는 graph dict에 key에 해당하는 값을 sort해준다. 하나의 행선지에 2개의 방향이 있을 수 있기 때문에, 이를 단일화 해준다. example) a->b, a->c의 경우 {'a':['b','c']}
#그리고 해당 key값에 대해서 sorting처리까지 해준다.
print("graph의 값 : ", graph)
answer = dfs(graph, N, "ICN", ["ICN"])
return answer