dtc03012   3년 전

제가 구현한 알고리즘은 일단 처음 주어진 배열로 scc를 만든다음

위상정렬을 하여

만약 a번째 scc에 최장 경로로 온 경로를 저장하여서 출력하게 했습니다.

왜냐하면 최장경로가 아닌 다른 경로로 왔을 경우에는 이게 위상정렬이므로 어떤 정점을 안 거치고 왔을 수 도 있기 때문입니다

혹시 반례가 있으면 가르쳐주십세요 ㅠㅠ

ehddml3   3년 전

저도 지금 풀고 있는데 같은 이유로 이런 케이스가 안되네요

1

3
101
011
001

dtc03012   3년 전

아오 ㅠㅠ 진짜 도저히 모르겠네요 ㅠㅠ 혹시나 푸시면 힌트라도 좀 알려주시면 감사하겠습니다..

dtc03012   3년 전

원래 scc로 돌리는걸 못하겠어요..

upple1   1년 전

아직 못 푸신 것 같아서 답글 남겨드립니다.

이 문제같은 경우 a->b->c로 가는 길이 있다고 판단되면 a->c 길이 없어도 됨을 알 수 있습니다.

이는 어떤 특정 알고리즘의 접근법이랑 유사합니다.


jhjh9501   1년 전

제가 엄청 고생했는데.. 윗분 말씀에 보충을 해서 설명을 하려고 합니다.

일단 SCC 간의 최적 경로.. 그러니까 연결되는 최적경로를 찾는데 위상정렬을 쓰면 안되고 플로이드-와샬을 써야하네요.

그 외의 최적경로를 찾는 알고리즘.. 경로값이 모두 양수니까 디엑스트라자 써도 괜찮을것같아요 제 생각에는.

위상정렬을 써서 찾는데 여러가지 방법이 있 겠지만..

제가 몇가지 시도 하다 마지막에 시도했던 방법은..  indegree가 0인 node들을 q에 넣고 돌리면서.

q 에 있는 애들의 next를 방문하면서 이 next들의 indegree들을 1씩 줄이고,

indegree가 0인된애들에 대해서 현재 - next 사이의 연결 경로를 만들어 주자. .이런거였는데,,,

결론적으로 말하면 연결 경로가 2개가 필요한 애들이 있어서 이러한 방법으로..하면 안되네요

얘를 들어서,  1, 2, 3, 4 node에 대해서

1>2, 2>4, 3>4 라고 합시다.. 위상정렬 결과는 1,2,3,4이고요

위 알고리즘대로 하면 3>4 만 연결을 하겠지만 사실은 2>4, 3>4 연결이 두개다 있어야 합니다. 

그럼 그냥 위상정렬되어있는 애들을 순서대로 방문하는건 안되냐? 그러면 무조건 모든 SCC들이 더 연결되도록 방문할수있으니 

조건에 위배되지 않잖아... 라고 할 수 있는데

문제가 두 개 있죠, 갈수없는 SCC 를 방문할 수 있겠죠 위 예시대로라면 2>3 은 방문하면 안되지만 위 방법대로 하면 방문하게됩니다.

위 문제만 해도 물론 방문할 수 없지만,

또 다른 문제는 최소 길을 방문할 수 없다는 점입니다.

1>3, 2>4 의 경우 위상정렬 결과가 1>2>3>4로 2개로 나타낼수있는데 위방법대로라면 4개가 필요하겠죠..

제가 고민한 내용을 정리할 겸 작성하였습니다.

도움이 되었으면 합니다.

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