102301394번 제출에 대한 반례를 찾고 계시는 것이 맞을까요? 그러면 다음과 같은 반례가 있습니다.
2150번 - Strongly Connected Component
102301394번 제출에 대한 반례를 찾고 계시는 것이 맞을까요? 그러면 다음과 같은 반례가 있습니다.
안녕하세요.
위 반례의 올바른 실행 결과가 아래가 맞을까요?
102301394번 제출에서도 틀린 결과가 아닌 올바른 결과가 나오고, 직접 손으로 따라가면서 생각해보아도 딱히 문제점이 생각나지 않습니다.
결국에는 타잔 알고리즘이라는 것이, 이미 스택에 있는 노드를 다시 한 번 만나게 되면 재귀를 풀어가면서 대표값(lowlink)를 갱신시켜주어서 같은 lowlink를 가지고 있는 노드들끼리 SCC를 이룬다고 이해했습니다.
분명 뭔가 잘못될 것이 있을텐데...도저히 감이 안잡힙니다ㅠㅠ
아니면 그냥 단순히 102301394번의 제출이 어딘가에서 단순한 실수가 있는 것일까요?
아, 제가 잘못 생각했습니다 유향 간선인데...
피곤해서 그런가 봅니다 헷갈리게 만들어서 죄송합니다ㅠㅜ
다른 반례는 저도 다시 생각해보겠습니다
반례 하나를 더 가져와보았습니다. 이번 반례는 확실한 것 같아요 :)
오! 반례 감사합니다.
근데 지금보니까 102301394번 제출은 그냥 DFS 함수 자체가 잘못된 것이었네요...
사실 제가 메인 글에서 궁금했던 것은 102308789번(방금 새로 제출했어요) 에 대한 반례입니다.
이 코드는 심지어 위 반례들도 모두 통과합니다.
최종적으로 low가 같다고 해서 무조건 SCC는 아닌걸까요? (low가 대표값의 역할을 하는 것이 아닌가요??)
다시 말하자면, 타잔 알고리즘에서 SCC를 발견 했을 시 스택에서 빼는 것 까지는 알겠는데 이때 자기 자신이 나올때까지 뺀 노드들을 SCC로 묶어주는 과정이 꼭 필요한가요? 나중에 묶어주면 왜 안될까요?
댓글을 작성하려면 로그인해야 합니다.
kkigon 9달 전 1
안녕하세요. 타잔 알고리즘을 구현해보다가 궁금한 점이 생겼습니다.
보통 다른 책이나 블로그들을 보면, 보통 lowlink이라는 리스트를 만들어서, 각 노드의 lowlink를 관리해주는 방식을 씁니다.
정석적인 구현에서는 보통 SCC를 발견했을 경우 스택에서 직접 노드들을 pop해주고, 즉시 이 pop된 노드들을 SCC로 따로 저장해줍니다.
여기서 문득 궁금증이 들었는데요,
lowlink 리스트를 일단 다 만들어 놓고, 맨 마지막에 이 lowlink 리스트를 보고 lowlink가 같은 것 끼리 묶어도 SCC가 되는 것 아닌가요?
이렇게 코드 구현을 하면 틀렸습니다가 나오는 것을 보니 일단 위 궁금증은 틀린 것 같기는 합니다.
그런데 반례를 못 찾겠습니다. 간단한 반례를 찾아주실 수 있으신가요?
감사합니다.