kkigon   9달 전

안녕하세요. 타잔 알고리즘을 구현해보다가 궁금한 점이 생겼습니다.

보통 다른 책이나 블로그들을 보면, 보통 lowlink이라는 리스트를 만들어서, 각 노드의 lowlink를 관리해주는 방식을 씁니다.

정석적인 구현에서는 보통 SCC를 발견했을 경우 스택에서 직접 노드들을 pop해주고, 즉시 이 pop된 노드들을 SCC로 따로 저장해줍니다.

여기서 문득 궁금증이 들었는데요,

lowlink 리스트를 일단 다 만들어 놓고, 맨 마지막에 이 lowlink 리스트를 보고 lowlink가 같은 것 끼리 묶어도 SCC가 되는 것 아닌가요?

이렇게 코드 구현을 하면 틀렸습니다가 나오는 것을 보니 일단 위 궁금증은 틀린 것 같기는 합니다.

그런데 반례를 못 찾겠습니다. 간단한 반례를 찾아주실 수 있으신가요?


감사합니다.

luckyandykang   9달 전

102301394번 제출에 대한 반례를 찾고 계시는 것이 맞을까요? 그러면 다음과 같은 반례가 있습니다.

kkigon   9달 전

안녕하세요.

위 반례의 올바른 실행 결과가 아래가 맞을까요?

102301394번 제출에서도 틀린 결과가 아닌 올바른 결과가 나오고, 직접 손으로 따라가면서 생각해보아도 딱히 문제점이 생각나지 않습니다.

결국에는 타잔 알고리즘이라는 것이, 이미 스택에 있는 노드를 다시 한 번 만나게 되면 재귀를 풀어가면서 대표값(lowlink)를 갱신시켜주어서 같은 lowlink를 가지고 있는 노드들끼리 SCC를 이룬다고 이해했습니다.

분명 뭔가 잘못될 것이 있을텐데...도저히 감이 안잡힙니다ㅠㅠ

아니면 그냥 단순히 102301394번의 제출이 어딘가에서 단순한 실수가 있는 것일까요?

luckyandykang   9달 전

아, 제가 잘못 생각했습니다 유향 간선인데...

피곤해서 그런가 봅니다 헷갈리게 만들어서 죄송합니다ㅠㅜ

luckyandykang   9달 전

다른 반례는 저도 다시 생각해보겠습니다

kkigon   9달 전

그래도 댓글 달아주셔서 감사합니다! 저도 더 찾아보겠습니다!

luckyandykang   9달 전

반례 하나를 더 가져와보았습니다. 이번 반례는 확실한 것 같아요 :)

kkigon   9달 전

오! 반례 감사합니다.

근데 지금보니까 102301394번 제출은 그냥 DFS 함수 자체가 잘못된 것이었네요...

사실 제가 메인 글에서 궁금했던 것은 102308789번(방금 새로 제출했어요) 에 대한 반례입니다.

이 코드는 심지어 위 반례들도 모두 통과합니다.

최종적으로 low가 같다고 해서 무조건 SCC는 아닌걸까요? (low가 대표값의 역할을 하는 것이 아닌가요??)

다시 말하자면, 타잔 알고리즘에서 SCC를 발견 했을 시 스택에서 빼는 것 까지는 알겠는데 이때 자기 자신이 나올때까지 뺀 노드들을 SCC로 묶어주는 과정이 꼭 필요한가요? 나중에 묶어주면 왜 안될까요?

kiwiyou   9달 전

스택에서 정점을 제거한 뒤에는 lowlink가 업데이트되지 않으므로, 같은 SCC에 속한 정점을 따로 저장해 둘 필요는 없습니다.

다만 dfs에서 중복 방문을 하지 않기 때문에, 스택에서 정점을 제거하는 순간에도 lowlink의 업데이트가 필요할 수 있습니다. 

preview

kkigon   9달 전

우와, 이런 반례가 있었군요!

덕분에 모든 궁금증이 해결되었습니다. 도움 주신 분들 모두 감사합니다!

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