후...반례를 찾았네요
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 될수밖에 없기때문에..
이방식이 정확한것이되네요
감사합니다
jhjh9501 4년 전 1
보통 책들에서 설명하는 DFS 방식은
DFS로 방문할 수 있는 모든 노드를 재귀적으로 방문한뒤..
방문할 수 있는 next가 없으면
topological_sort 와 같은 큐에 데이터를 집어넣고,
이를 역순으로 표시하는 건데요..
저는 def 함수 시작할때,
다른 노드를 방문하기 전에 현재 노드를 stack에 집어넣고
노드 방문이 다 끝나면 topological_sort 큐에 이 stack을 집어넣었습니다.
그 후, 이 topological_sort 큐를 역순으로 했는데...
왜 틀리는 경우가 생기는 걸까요??논리적으로 문제가 없어 보이는데
제가 정리한 dfs 함수와 정렬 방식입니다
이 방식이 진짜 왜 문제가 있는지모르겠네요 ㅠㅠㅠ제가 생각해본 다양한 테스트에서 모두 문제가없었는데..