[자료구조] 13-3. 깊이 우선 탐색 알고리즘의 응용 (2)

이중 연결 성분을 찾는 알고리즘은 크게 3단계로 나뉜다.

1. 분절점 정의

1) dfn 정의

2) back edge 정의

3) 분절점 정의

2. 분절점 찾기

3. 분절점을 이용해 그래프를 이중 연결 성분으로 분해하기

dfn은 depth-first number의 약자이며, dfs를 하면서 버텍스를 방문하는 순서를 의미한다.

만약 위의 그래프에서 3번부터 dfs를 한다고 생각해보자. 버텍스 3에서 갈 수 있는 곳은 1 4 5가 있는데, 숫자가 낮은 것부터 방문하므로 1-2-4-0의 순서로 방문할 것이다. 

그럼 dfn은 버텍스 3부터 1-2-4-0까지 0, 1, 2, 3, 4로 부여된다. 맨 마지막에 3번으로 다시 돌아오면 5-6-7-8-9를 방문할 것이다. 이 순서대로 또 5, 6, 7, 8, 9번 dfn이 부여된다.

dfn을 더 자세히 살펴보기 위해, dfs가 수행되는 순서대로 그래프를 재조합해보았다. 파란색 선을 신장 트리라고 하는데 이 신장 트리를 트리의 모양에 맞게 다시 그린 것이다.

dfs에서 만들어진 신장 트리에서, 어떤 버텍스 v가 u의 조상이라면, dfn의 값은 더 작다. 버텍스 5와 7을 비교하면 5는 7의 조상이며 dfn이 7보다 작다.

신장 트리에 속하는 엣지를 tree edge, 신장 트리에 속하지 않는 엣지를 non-tree edge라고 부른다. 백 엣지는 서로 부모 관계가 아닌, 조상 관계의 두 버텍스를 연결하는 논 트리 엣지이다.

그럼 아까의 그래프에서 파란색 굵은 엣지는 신장 트리이므로 트리 엣지가 된다. 3 4와 5 7을 연결한 하얀색 엣지는 신장 트리에 포함되지 않는 논 트리 엣지를 의미한다.

2개 이상의 자식 노드를 가지고 있는 깊이 우선 신장 트리의 루트 노드는 분절점이라고 부른다. 즉, 3번 버텍스는 분절점이다.

2번 버텍스는 제거해도 다른 부분들이 분해되지 않는다. 2번 버텍스의 자식 노드가 2번 버텍스의 조상으로 가는 백 엣지를 가지고 있기 때문이다. 4번 버텍스는 제거하면 두 개로 갈라진다. 4번의 차일드 노드는 그 부모로 올라가는 백 엣지를 가지고 있지 않기 때문이다.

어떤 버텍스가 그 후손으로 내려갔다가 한 번의 백 엣지를 통해 해당 버텍스의 조상으로 올라가는 경로를 back path라고 한다. 4번 버텍스는 자식인 0으로 내려갔지만 더 이상 올라갈 길이 없다. 그러므로 4번 버텍스는 백 패스가 없다고 할 수 있다.

2번 버텍스는 후손인 4로 내려가서 4에 있는 백 엣지를 통해 3으로 갈 수 있다. 그리고 이 3은 2의 조상이다. 그러면 2번 버텍스는 백 패스가 존재한다고 말할 수 있다.

특정 버텍스가 분절점이냐는 질문은 '그 버텍스는 백 패스를 가지고 있는가'로 바꿀 수 있다. 백패스를 통해 올라갈 수 있는 가장 높은 버텍스가 무엇인지 보면 백패스 유무를 알수 있다. 백 패스를 통해 최대한 높이 올라가도 조상까지 올라가지 못한다면, 그 버텍스는 분절점이다.

이는 세 가지 경우로 분류할 수 있다.

1. 버텍스 u와 그의 후손에 백 엣지가 없는 경우. u가 분절점이 된다.

2. 버텍스 u가 u의 부모로 올라가는 백 엣지를 가지는 경우. 이 경우 u는 분절점이 아니다.

3. 버텍스 u 자기 자신에게 백 엣지가 있는 경우. 백 엣지가 있어도 이 버텍스를 제거하면 두 개로 갈라지므로, 분절점이다.

내 조상으로 올라가는 백 패스가 존재하는지 쉽게 찾기 위해 low라는 값을 정의한다. low는 한 버텍스에서 한 번의 백 패스를 통해 올라갈 수 있는 가장 높은 버텍스의 dfn이다.

1. 백 엣지와 백 패스가 없으므로 자기 자신의 dfn이 low값이 된다.

2. w를 통해 v까지 올라가므로 low(w)는 v의 dfn이다.

3. 자기 자신의 백에지를 통해 올라갈 수 있는 버텍스의 dfn이 자기 자신의 로우값이다.

따라서 low 값은 위와 같이 정의된다.

- 어떤 버텍스 w가 u의 차일드 노드라는 전제 하에, 버텍스의 dfn

- 이 버텍스의 차일드 노드의 로우 값 중에 제일 작은 값

- 버텍스의 백엣지를 통해 올라갈 수 있는 값 중에 가장 작은 dfn

중 제일 작은 값이다.

- 0번 버텍스의 low 값

백 엣지도 백 패스도 없기 때문에 로우는 4가 된다.

- 4번 버텍스의 low 값

4번 버텍스에는 한 번의 백 엣지를 통해 올라갈 수 있는 버텍스가 3이기 때문에 3의 dfn인 0이 4번의 로우 값이 된다. 자기 자신의 dfn인 3 / 차일드 노드의 로우 값인 4 / 백 엣지로 올라가서 갈 수 있는 버텍스의 dfn인 0 중에 가장 작은 값을 선택하므로 0인 것이다.

- 2번 버텍스의 low 값

자기 자신의 dfn인 2 / 자식의 로우 값 / 백 엣지는 없으므로 그 중에 작은 값인 0이 low가 된다.

따라서 특정 버텍스가 분절점인지 판단하는 과정은 이러하다.

- 버텍스 u가 백패스를 가지고 있는가?

- 그 백패스를 통해 올라갈 수 있는 가장 높은 조상 버텍스는 무엇인가?

- 자기 자신의 dfn과 차일드의 로우값을 비교한다.

1. 백패스가 있는 경우

- u의 dfn이 있고, 차일드인 w가 백패스를 가지고 있다면 이때의 로우값은 가장 높이 올라갈 수 있는 버텍스 v의 dfn이다.

- v는 u의 조상이기 때문에 dfn이 더 작다.

- low(w)와 dfn(v)가 같이 때문에 dfn(u) > low(w)라는 관계가 성립한다.

- 따라서 자식 노드의 로우값이 자신의 dfn보다 더 작다면, 이 버텍스는 분절점이 아니다.

2. 백패스가 없는 경우

- 자식 노드인 w의 로우 값은 dfn(w)이다.

- u가 조상이므로 dfn(u) <= low(w)이다.

- 이런 관계를 만족할 경우는 u가 분절점이라고 말할 수 있다.

따라서 분절점인지를 구분하려면, 특정 버텍스와 그 버텍스의 차일드 노드가 가진 dfn과 로우를 비교한다.

버텍스 3는 분절점일까?

4의 dfn과 차일드인 0의 로우 값을 비교한다. 3<4이므로 4번은 분절점이 된다.

2번 버텍스는 분절점일까?

2번 버텍스의 dfn과 차일드 노드인 4의 로우를 비교하면 2>0이므로 분절점이 아니다.

1번 버텍스도 dfn과 차일드인 2번의 로우를 비교하면 분절점이 아니다.

7번 버텍스의 dfn은 7이고, 두 차일드 중에 작은 로우 값은 8이다. 8번 버텍스의 로우는 9이므로 7<8, 즉 7번 버텍스는 분절점이다.

5번 버텍스의 dfn과 자식인 6번 버텍스의 로우 값을 비교하면 같다. 더 크지 않기 때문에 결국 이 버텍스도 분절점이 맞다.

따라서 루트 노드인 3번과 4, 5, 7번은 모두 자식의 로우 값이 자기의 dfn보다 크거나 같기 때문에 분절점이다.

분절점을 그래프에 표현하면 이와 같이 된다. 

분절점을 기준으로 그래프를 분해하면 이렇게 많이 쪼개진다. 이렇게 이중 연결 성분으로 분해할 수 있다.

이중 연결 성분으로 분해하는 과정을 코드로 구현해보자. 이 과정은 dfs를 변형해서 구현한다. dfn을 계산하고 -> low를 계산한 뒤 -> 분절점을 계산하는 순서다.

1. dfn 계산

- visit 대신 dfn과 로우를 저장하는 배열을 만든다.

- 버텍스의 값을 -1로 초기화하면 아직 방문하지 않은 버텍스가 된다. visit를 false로 만드는 초기화 과정과 같다고 할 수 있다.

- dfs(u) 대신 dfs(u, v)를 호출한다. 부모 노드를 함께 보내는 것이다.

- 방문 순서를 나타내는 num을 선언하고 0으로 초기화한다. 원래는 방문하지 않은 버텍스는 dfs를 수행하고, 수행했으면 true로 바꿔주는 연산이었다. 하지만 이제는 visit 대신에 dfn이라는 변수를 만들고, dfs를 수행하는 순서를 저장하기 위해 그 순서를 관리하는 num을 만드는 것이다.

- dfn을 호출할 때마다 num을 저장하고, 그 다음 num은 1을 증가시킨다.

- 아직 방문하지 않은 버텍스 즉, dfn이 0보다 작은 경우는 dfs를 수행해달라고 호출하면 된다.

2. low 계산(dfs2 함수)

- low 값을 자기 자신의 dfn 값으로 초기화 한다.

- dfs가 끝난 다음에 자기 자신의 로우 값과 자식 노드의 로우 값을 비교해서 더 작은 값을 자기 자신의 로우 값으로 저장한다.

- 부모 노드와 같지 않은지 점검한다.

3. 분절점 계산

- low 값 계산 후 자기 자신의 dfn 보다 자식 노드의 로우 값이 더 크거나 같으면 즉, low[w] >= dfn[u]이면 이 버텍스는 분절점이 된다.

4. 이중 연결 성분 찾기(스택 활용)

- 자기 자신과 자식 노드를 스택에 저장한다.

- dfs를 수행하고 끝이 나면 low 값을 계산한다.

- 자식의 로우 값이 자기의 dfn보다 크거나 같으면 즉, u가 분절점인지 체크한다.

- 이 버텍스까지 오면서 스택에 저장했던 모든 엣지들을 다 출력한다.

깊이 우선 탐색의 시간 복잡도는 O(n+m)이었다. 이중 연결 성분을 찾는 알고리즘도 dfs를 통해 수행된다. 따라서 이중 연결 성분 알고리즘도 O(n+m)이 된다.