jhjh9501   4년 전

보통 책들에서 설명하는 DFS 방식은 

DFS로 방문할 수 있는 모든 노드를 재귀적으로 방문한뒤..

방문할 수 있는 next가 없으면

topological_sort 와 같은 큐에 데이터를 집어넣고,

이를 역순으로 표시하는 건데요..

저는 def 함수 시작할때,

다른 노드를 방문하기 전에 현재 노드를 stack에 집어넣고

노드 방문이 다 끝나면 topological_sort 큐에 이 stack을 집어넣었습니다.

그 후, 이  topological_sort 큐를 역순으로 했는데...

왜 틀리는 경우가 생기는 걸까요??논리적으로 문제가 없어 보이는데


제가 정리한 dfs 함수와 정렬 방식입니다

이 방식이 진짜 왜 문제가 있는지모르겠네요 ㅠㅠㅠ제가 생각해본 다양한 테스트에서 모두 문제가없었는데..

jhjh9501   4년 전

후...반례를 찾았네요

8 8 

1 2 

2 3

 3 7 

3 8 

2 6 

1 4

 4 5 

6 3

으로 하면 정답이 안나옵니다...

음..완료 되지 않았을때 업뎃하는게 어떤 위험이 있는지 알게되었는데,

위 예시의 경우 2>3, 2>6, 6>3 이렇게 세 간선이 있네요. 간선 입력 순서가 바뀌면 또 답을 찾지만..

2>3을 먼저 방문해버리면 6다음에 3이 방문되어야하는데 그냥 집어넣어버립니다


저는 DFS 트리에서 조상 하나를 방문하면, 걔를  stack에 넣고 그 하위를 방문하면 위상 순서가 된다고 생각했는데,

하위에 있는 애들끼리 조상 관계가 있을 때, 이 순서가 뒤바뀌어서 들어가면 오류가 나네요 

조상들을 전부 확인안하고 들어가버릴 염려가있네요

반면 finished 한 애만 집어넣게되면..

조상들을 전부 확인안하고 시작을 하더라도 결국 dfs 돌면서

조상이 마지막에  finished 될수밖에 없기때문에..

이방식이 정확한것이되네요

감사합니다

댓글을 작성하려면 로그인해야 합니다.