돌이 코딩하는 방

서론 SCC(Strongly Connected Components)를 구할 때는 크게 타잔 알고리즘과 코사라주 알고리즘을 사용한다. 그 중에서도 코사라주 알고리즘을 사용하는 편이다. 최근에 코사라주 알고리즘의 정당성에 대한 증명을 알게 되어서, 나의 블로그에는 알고리즘의 정당성에 관한 내용이 하나도 없는 것 같아서 글을 적어보려고 한다. 먼저 읽고 와야하는 글 - SCC와 코사라주 알고리즘 - DFS ordering (혹은 Euler Tour. 꼭 이 글 안 봐도 됨) 사전 준비 왼쪽과 같은 그래프에서 오른쪽과 같이 색깔별로 그룹을 묶었다. 이는 위의 글에서도 알 수 있듯이 코사라주 알고리즘을 통해 얻은 결과이며, 이 그룹이 SCC가 맞음을 증명할 것이다. 어떤 그룹이 SCC가 맞다는 것을 증명하기 위해..

'Tree에서는 Centriod를 잡고 생각하면 편하고 그래프에서는 SCC를 잡고 생각하면 편하다.' 라는 말이 있다. 사실 수준급의 그래프 문제를 많이 풀어본 것이 아니라서 별로 공감은 안되지만, SCC가 정말 좋은 테크닉이라는 것은 인정하고, 저러한 말이 나올 정도로 굉장히 유용하게 쓰일 수 있다. 이번 포스팅은 그러한 SCC에 대해서 설명하려고 한다. SCC scc란 무엇일까? scc는 strongly connected component로 약자를 풀어내면 해석이 되는 다른 줄임말과 다르게 바로 알 수가 없다. 보통 방향그래프에서의 scc를 말하며, scc는 아래의 두가지 조건을 만족하는 서브 그래프이다. 1. 한 scc안에 속한 임의의 어떤 한 노드 A와 다른 한 임의의 노드 B에 대해서 A에서 B..