[Algorithm] 단절점을 찾는 알고리즘과 단절선을 찾는 알고리즘이 미세하게 다른 이유

단절점과 단절선의 개념에 대해서는 스킵하겠습니다. 추후에 시간이 되면 올리겠습니다 ~

 

 

본론으로 들어가서 단절점을 찾는 알고리즘과 단절선을 찾는 알고리즘이 왜 미세하게 다른 것일까요? 처음 단절점의 개념을 접하고나서 여러 블로그를 찾아봤었는데 단절선은 단절점 알고리즘에서 약간 변형만 하면 된다고 써놓고 코드만 올려놓은 블로그들이 대다수였습니다;;; 저같은 단절점 초보에게는 너무나도 매정한 설명이었습니다. 

 

결론적으로 말하면 제가 이 포스팅을 하는 이유는 왜 단절선을 찾을 때는 부모 정점로 가는 간선을 제외하고 찾아야 하는가? 였습니다.

 

단절점을 찾을 때는 시작 정점에서 DST를 만들어 가면서 한 정점에서 부모 정점을 포함하여 뻗어나갈 수 있는 정점의 번호 중 가장 작은 값을 리턴시켜주는 알고리즘을 사용했습니다. 단절점에서는 부모 정점을 비교해도 상관없는데 왜 단절선에선 부모 정점으로 가는 간선을 비교하면 안되는 것일까?  

 

 

계속 고민한 결과 드디어 찾아냈습니다!

 

 

이 그림을 예시로 들어볼게요! 자 2번 정점은 단절점일까요? 아닐까요? 

 

정답은 단절점이 맞습니다. 2번 정점이 없는 순간 1번 정점 하나인 그래프와 4번과 3번 정점이 이루는 그래프, 총 2개의 그래프로 나누어지기 때문이죠! 자 그럼 바로 아래 그림을 보실까요?

 

 

 이 그림에선 2번 정점이 단절점일까요? 아닐까요? 역시 단절점입니다! 윗 그림과 똑같은 경우기 때문이죠. 제가 왜 이 그림들을 보여주었나 의아하실텐데요. 2번 정점이 단절점인지 아닌지 판단할 때 2가지 값으로 판단하게 되는데 바로 부모의 DST 번호와 2번 정점의 자식들에게서 오는 DST 번호입니다. 윗 그림에선 4번 정점이 2번 정점과 연결되어 있지 않기 때문에 3을 리턴하고 3번 정점은 2를 리턴합니다. 따라서 2번정점이 가지고 있는 1이라는 값보다 크게 되므로 단절점이 됩니다.

 

장황하게 설명했지만 단절선에서는 위 두 그림에서 다른 결과가 나오게 됩니다.

 

 

이 그림에서 2 ->3으로 가는 간선은 단절선이 될 수 없지만!

 

이 그림에서는 가능하기 때문입니다. DST를 돌며 순번을 비교할 때 부모 정점의 순번까지 비교하여 가지고 있게 되면

 

이 예제에서와 같이 사이클이 있는 경우도 단절선으로 착각해버리죠. 

 

 

단절점 알고리즘을 그대로 적용하면 2번 정점에서 3번 정점으로 가는 간선을 단절선으로 확정해버립니다. 단절선이 아닌데도 불구하고 말입니다.

 

 

 

따라서 단절선은 저런 경우가 없게 만들기 위해 한 정점에서 다음과 같이 판단합니다.

 

한 정점에서 부모 정점으로 가는 간선을 제외하고 남은 연결된 간선들 중에서 되돌아오는 최소 순번값이 본인의 순번값보다 크다면 단절선이라고 판단합니다.

 

제가 단절점 단절선의 개념 설명없이 너무 제 궁금증 해결됐다고 막쓴거 같은데 뭐 어쨌든 이렇습니다...