leechhe   1년 전

DFS로 탐색 후 return 할 때 dag 배열에 push 하고

순서를 뒤집어서 답을 찾습니다.

순서가 불가능한 경우는 finished 배열로 체크를 하였습니다. 나름 만들어서 돌려봤는데... 부탁드려요 ㅠㅠ

algoshipda   1년 전

순서로 불가능한 경우는 위상정렬이 불가능 한 경우를 말하는 건데, 위상정렬은 그래프에 사이클이 존재하면 불가능합니다.

leechhe   1년 전

algoshipda 답변 감사합니다.

사이클이 존재하는 경우는 finished 배열로 체크를 하였습니다.

finished는 각 dfs(cur)가 끝날 때 true로 세팅합니다. dfs로 탐색을 하다가

1. 이미 방문을 했지만

2. 아직 함수가 종료되지 않은 경우

를 찾았을 때 사이클이 존재한다고 판단했습니다. 혹시 여기에 오류가 있나요?


algoshipda   1년 전

DFS를 한 컴포넌트에 대해서만 돌려서 그런것 같아요.

leechhe   1년 전

전체 그래프는 1번부터 시작하는데 그래프를 만들 때 각 PD들의 리스트 시작을 0번 노드와 연결하여 DFS(0)로 하였습니다.

다 탐색할 수 있지 않나요?

그래프가 연결 그래프가 아니라서 컴포넌트가 여러 개일 때를 말씀하신 듯합니다

그리고 0번 노드에 연결될 노드는 항상 indegree가 0인 노드들만이어야 하지 않을까 싶어요.

leechhe   1년 전

portableangel algoshipda 해결했습니다 감사합니다 :)

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