프로그래머스의 연습문제 여행경로의
풀이와 자세한 설명을 공유합니다.
링크
풀이 코드
from collections import defaultdict
def solution(tickets):
# 알파벳 순서대로 반환해야 하기 때문에, 속편하게 먼저 정렬을 해줍니다.
tickets.sort()
# 방문한 도시를 기록할 리스트를 만듭니다.
rev = []
# 그래프를 생성합니다. defaultdict를 사용하면 편리합니다.
graph = defaultdict(list)
for depart, arrive in tickets :
graph[depart].append(arrive)
# 대망의 DFS 함수. 출발 도시를 input으로 받습니다.
def DFS(start) :
#그래프의 출발도시로부터 남은 도착지가 있다면
while graph[start] :
# DFS함수를 호출합니다. 이 때 pop()을 사용해서 그래프에서 방문도시를 삭제합니다.
DFS(graph[start].pop(0))
# while문이 끝나면 방문한 도시를 기록합니다. 아래에 설명합니다.
rev.append(start)
# 첫 출발지는 조건으로 주어진 "ICN"입니다.
DFS("ICN")
# 저장한 값을 거꾸로 반환. 아래에 설명합니다.
return rev[::-1]해설(1차)
풀이의 개요를 설명하겠습니다.
코드에 대부분의 설명을 적어놨지만,
먼저 DFS를 사용하여 방문이 가능한 모든 도시에 방문하는 것을 알 수 있습니다.
그리고, 방문한 도시를 리스트에 저장할 때는
while문이 종료되는 시점을 기준으로 하므로
depth가 가장 깊을 때인 가장 마지막 지점을 방문했을 때가
리스트에 처음으로 저장되는 값이고, 마지막으로 저장되는 값은 첫 출발지인 "ICN"인 것을 알 수 있습니다.
의문
그러나 저는 이런 의문을 가졌습니다.
- 알파벳 순서대로 방문하면 모든지점을 방문할 수 없는 경우가 생긴다.
- 이러한 방문도시 리스트의 저장값이 틀리게 되지 않을까?
이러한 의문을 갖게 된 것은 아래의 그림과 같은 경우입니다.
문제의 조건 : {"A": ["B"], "B":["C","D"], "C":["D"], "D":["A","D"]}
이 케이스에서 출발지 D에는 도착지 A,B가 있습니다.
그러나 알파벳 순서대로 진행하려고 하면 D->B 와 B->D를 방문하지 못하게 됩니다.
또, 이 경우 DFS의 호출 순서를 적어보면 아래와 같습니다.
# 문제의 조건
DFS(A) :
DFS(B) :
DFS(C) :
DFS(D) :
DFS(A) :
DFS(B) :
DFS(D) :이는 DFS(A) 뒤에 DFS(B),(D) 가 호출되므로
이 경우 리스트에 순서대로 저장되는 값은
- D -> B -> A -> D -> C -> B -> A
이를 결과를 거꾸로 돌려보면
- A -> B -> C -> D -> A -> B -> D 입니다.
우리가 생각했던 A로 끝나는 경로가 아닌 A->B의 없는 경로가 새로 만들어지는 것처럼 보입니다.
뭐가 문제일까요?
해설(2차)
문제는 중간의 DFS(A)를 제외한 다른 모든 DFS 함수들이,
DFS함수의 호출 순서를 거꾸로한 그대로 저장되므로
DFS함수의 발생 순서를 뒤집은 그대로 리스트 저장이 발생할 거라는 착각입니다.
rev.append(start)는 DFS 함수 내에서 호출한 while문이 끝나면 호출됩니다.
따라서, 여기에서 잘 보면 중간의 DFS(A)는 호출할 다른 도착지점이 없어 while문이 바로 끝나므로 append(A)가 바로 발생하고, 이로써 rev에 처음 저장되는값이 A가 되는 것입니다.
DFS(A) :
DFS(B) :
DFS(C) :
DFS(D) :
# 여기에서 DFS(A)가 끝난다. 따라서 rev에 A가 가장 먼저 저장된다.
DFS(A) :
# 그 다음으로는 B가 저장되는 것이 아니고, D가 저장되고 B가 저장된다.
DFS(B) :
DFS(D) :이 구조를 잘 생각해보면 우리가 어딘가에 도착했을 때 더 나아갈 지점이 없을 때,
중간에 다른 곳으로 뻗을 수 있는 가지(node)가 남아있으면 그 방향으로 진행하는 것을 알 수 있습니다.
생각해보면 이 개념이 바로 DFS입니다.
결론
저는 이렇게 append()함수의 위치를 조절하는 것만으로 우리가 원하는 조작을 할 수 있다는 데에 약간 희열을 느꼈습니다.
그러나 이를 다 그려보느라 시간을 몇시간은 날려먹었기 때문에, 다른분들은 시간낭비가 없으시길 바라며..
글을 마칩니다.
