책에는 DFS를 아래와 같은 코드로 구성하였지만
graph={"A":{"B","C"},"B":{"A","D"},"C":{"A","D","E"}, "D":{"B","C","F"},
"E":{"C","G","H"}, "F":{"D"},"G":{"E","H"},"H":{"E","G"}
}
def dfs(graph, start, visited=set()):
if start not in visited:
visited.add(start)
print(start, end=' ')
nbr=graph[start]-visited
for i in nbr:
dfs(graph, i, visited)
내 혼자힘으로 구현한 코드는 아래와 같고 문제 없이 잘 동작하였다.
graph={"A":{"B","C"},"B":{"A","D"},"C":{"A","D","E"}, "D":{"B","C","F"},
"E":{"C","G","H"}, "F":{"D"},"G":{"E","H"},"H":{"E","G"}
}
def dfs(graph, start, visited=set()):
visited.add(start)
print(start, end=" ")
for i in graph[start]:
if i not in visited:
print(i, visited)
dfs(graph, i, visited)
dfs(graph, 'A')여기서 내가 가진 의문은 파이썬의 내장자료 구조인 SET인 visited이다.
내가 짠 코드에서 if i not in visited: 라는 코드가 있는데 나는 처음의 visited가 재귀를 거친후 반환되어 다시 for문으로 돌아와 if i not in visited를 거칠때 visited set안의 원소는 그대로 이전과 그대로일 것이라고 생각하였다. 하지만 그렇지 않다. 그 증거로는 위 코드를 실행한 아래와 같은 결과이다.
아래의 그림과 같은 순서로 탐색이 이루어지도록 많이 돌려서 나온 결과물이다. 결과에서처럼 A->B->D->C->E->G->H->F의 순서로 탐색이 이루어지고 있다. 여기서 주목할 것은 E를 탐색하고 한번도 방문하지 않은 G로 진입한후 print한 visited에는 {A, B, C, D, E}가 담겨있고 이에 따라 순서대로 G와 H를 방문한다. H를 집입하는 시기에 visited에는 {A,B,C,D,E,G,H}가 들어가 있는것은 당연하다. 그리고 H에서 더이상방문할 정점이 없으므로 H를 호출한 G로 되돌아 오고 G에서도 E,H를 모두 방문한 상태이므로 E로 되돌아온다. 여기서 visited의 상태가 이전처럼 [A,B,C,D,E]이라면 H를 방문하는것이 맞다.(G는 방금 반복문을 통과했으므로 패스!)하지만 위의 결과를 보면 알수 있듯이 H를 다시 방문하지 않는다. 이말은 곧 visited의 상태가 변했고 그 변한 visited에서 구체적인 visited의 원소를 차례차례검사한다는 것이다. 즉, if i not in visited는 if i not in [A,B,C,D,E] 인 상태로 멈춰 있는 것이 아니라 if문에 접근할 때마다 갱신된 visited에서의 원소를 차례차례검사한다는 것이다.
