티스토리 뷰
Articulation Point : 단절점
앞으로의 논의는 하나의 컴포넌트(connected component)로 구성된 무방향 그래프에 대해서 진행됩니다.
먼저 아래 무방향 그래프에서 단절점(절단점)을 파란색 테두리로 나타내었습니다.
그림을 보고 직관적으로 알 수 있듯이 단절점은
그 정점을 제거했을 때 그래프가 두개 이상으로 나누어지는 정점을 말합니다.
즉 제거했을 때 그래프의 connected component가 증가하는 정점을 말합니다.
그럼 어떻게 이 단절점을 찾을 수 있을까요?
가장 단순하게 생각해보면 점을 하나씩 없애보고 컴포넌트가 둘로 나눠졌는지 조사하는 것입니다.
N : 정점의 개수, M : 간선의 개수라 할때 이 방법의 시간 복잡도는 없앨 정점을 선택하는데 N, 그래프 전체를 dfs탐색하여 컴포넌트가 둘로 나눠졌는지 여부를 조사하는데 N+M이 걸리므로 전체 시간 복잡도는 O( N(N+M) )으로 나타낼 수 있습니다.
이보다 더 빠르게 할 수는 없을까요?
만약 단절점이 다른 점들과 구분되어 가지는 고유한 특징을 찾을 수 있다면 이를 적용하여 더 빠른 방법을 모색할 수 있을 것입니다.
그러면 어떤 특징이 다른정점과 단절점을 구분 지어줄까요?
왜 오렌지색 점은 단절점이 아니고 파란색점은 단절점이 될까요?
해당 정점에 연결된 간선만 보고 그 정점이 단절점인지 구분할 수 있을까요?
안됩니다. 해당 정점에 연결된 간선만 봐서는 절대 알 수 없을거 같습니다.
해당 정점에 연결된 정점이 다시 어떻게 연결되어 있는지까지 봐야합니다.
그러면 이제 직관적으로 우회로라는 관점에서 생각해봅시다.
아래 그래프에서 빨간색 정점을 기준으로 이와 인접한 인접한 정점을 하늘색 정점이라 할때
모든 하늘색 정점 쌍 사이에 빨간색 정점을 사용하지 않는 우회 경로가 존재할 경우 이 정점은 단절점이 되지 않습니다.
즉 하늘색 정점 사이에 단 한쌍이라도 빨간색 정점을 사용하지 않는 우회로가 존재하지 않으면 이 정점은 단절점이 됩니다.
첫번째 그림은 빨간색 정점이 단절점인 경우 입니다.
두번째 그림은 빨간색 정점이 단절점이 아닌 경우 입니다.
이때 모든 하늘색 정점 쌍 사이에 빨간색 정점을 지나지 않는 우회로가 존재함을 확인할 수 있습니다.
이제 단절점이 다른 정점과 구분되어 가지는 특징을 찾았습니다.
그러나 각 빨간색 정점에 대한 보라색 정점 사이에 빨간색 정점을 사용하지 않는 우회로가 있는지 찾아 보는게
위에서 언급한 O( N(N+M) ) 시간복잡도를 가지는 단순한 방법보다 훨씬 시간이 많이 걸리고 복잡할거 같습니다.
이를 타개할 방법으로 임의의 점에서 DFS탐색을 시작해서 방문하는 순서로 정점에 새로 번호를 매기고 생각해봅시다.
아래 그림은 위 그래프를 1번 정점을 루트로 하는 DFS스패닝 트리로 나타낸 것입니다.
(왼쪽에 정점 번호, 오른쪽에 DFS탐색시 발견순서, 화살표가 있는 간선은 DFS탐색시 사용된 간선, 점선으로 표시된 간선은 DFS탐색시 사용되지 않은 간선을 표시했습니다.)
cf) 이와 같이 DFS탐색을 하여 그래프를 트리로 구성한 것을 DFS스패닝 트리라고 합니다.(그래프 간선의 분류 게시물 참고)
그래프를 DFS스패닝 트리로 구성하면 인접한 정점사이에 연속된 번호를 부여할 수 있고 사이클이 없는 트리를 구성하여 순차적인 개념을 적용할 수 있기 때문에 그래프를 분석하는데 많이 사용됩니다.
이때 A번재 방문 집합은 반드시 하나의 컴포넌트로 구성되어 있습니다.
따라서 A번째 이후로 방문된 모든 정점이 모두 A번째 방문 이전 정점에 A번째 방문 정점을 사용하지 않고 도달할 수 있다면 A번째 방문 정점을 없애도 모든 정점이 하나의 컴포넌트를 이루어짐을 알 수 있습니다.
반대로 A번째 이후로 방문된 정점 중 하나라도 A번째 방문 이전 정점에 A번째 방문 정점을 사용하지 않고 도달할 수 없다면 A번째 방문 정점은 단절점입니다.
아래 그림에서 4째 방문된 정점인 5번 정점을 A번째 정점이라 하고 빨간색으로,
A번째 이전에 방문된 정점을 하늘색으로 A번째 이후에 방문된 정점을 핑크색으로 나타내었습니다.
빨간색 정점은 단절점이 아닌데 이때 모든 핑크색 정점은 빨간색 정점을 사용하지 않고 하늘색 정점에 도달할 수 있는 것을 확인할 수 있습니다.(간선의 화살표는 DFS탐색의 진행 방향을 의미하는 것입니다. 아래 그래프는 무방향 그래프이기 때문에 화살표와 무관하게 경로로 모든 간선을 사용할 수 있습니다.)
위 논리에서 따로 처리해줘야 할게 하나 있습니다.
바로 DFS스패닝 트리에서 루트노드에 해당 하는 노드인데요
이 루트 노드의 경우 이전에 방문한 노드가 없기 때문에 위 논리를 적용할 수 없습니다.
루트 노드의 경우 언제 절단점이 되는지를 관찰해보면 루트 노드의 자식 노드의 수가 2개 이상일 때 바로 절단점이 됨을 쉽게 관찰 할 수 있습니다.
따라서 다음과 같이 절단점 판별 논리를 정리할 수 있습니다.
정점 A가 루트 노드 일때
자식 수가 2이상일때 절단점
정점 A가 루트 노드가 아닐 때
정점 A의 자식 노드가 정점 A이전에 방문한 노드에 정점 A를 거치지 않고 도달할 수 없으면 절단점
이를 코드로 구현하기 위해 아래와 같이 함수와 변수를 정의합니다.
1. int dfs(int A, bool isRoot) : A의 자식 노드가 A를 거치지 않고 도달할 수 있는 정점 중 가장 먼저 dfs함수가 방문한 정점을 반환한다.
isRoot는 정점 A가 루트노드인지를 나타냅니다.
2. 정점 i가 DFS탐색에서 발견된 순서 : discovered[i]
3. 정점 i가 절단점인지 여부 : isCutVertex[i]
백준 온라인 저지 11266번 단절점 문제에 대한 코드를 작성해 보겠습니다.
Bridge : 단절선
단절선이란 그 간선을 제거했을 때, 그래프가 두개이상으로 나누어지는 간선입니다.
즉 제거했을 때 그래프의 connected component의 개수가 증가하는 간선을 말합니다.
단절선의 정의는 단절점의 정의와 매우 유사합니다.
따라서 단절점을 구하는 알고리즘을 조금만 변경하면 단절선을 구할 수 있는데요
이번에도 우회로 관점에서 생각해봅시다.
DFS스패닝트리를 구성했을 때 A번째로 방문한 정점으로 내려가는 간선이 단절선이 되기 위해서는
이 간선을 제외했을 때 A번째 정점을 포함해서 A번째 이후로 도달한 모든 정점에서
A번째 이전의 정점에 도달할 수 없어야합니다.
이를 만족하는 간선은 트리간선(tree edge)이 됩니다.
따라서 위 절단점 조건을 만족시키기 위해 단절점을 얻는 코드에서 dfs함수의 정의를 다음과 같이 변경하면 단절점을 간단하게 구할 수 있습니다.
int dfs(int A, int parent) : A와 A의 자식 노드가 A에서 parent노드로 가는 간선을 사용하지 않고 도달할 수 있는 정점 중 가장 먼저 dfs함수가 방문한 정점을 반환한다.
백준 온라인 저지 11400번 단절선 문제에 대한 코드를 작성해 보겠습니다.
- Total
- Today
- Yesterday