[c++] 백준 - 단절점(11266) [단절점 이론]

1. 문제

2. 입출력

3. 예제 입출력

4. 문제 해설

혼자 푼 문제는 아니다. 애초에 특수한 단절점과 단절선에 대한 이론을 알고 있어야해서 인터넷에서 단절점과 단절선에 대한 이론을 찾아본 후 풀었다. 

https://jason9319.tistory.com/119

단절점(Articulation Point)와 단절선(Bridge)

위의 블로그에서 많은 도움을 얻었다. 

 

내가 이해한 바를 다시 정리해 말하면 다음과 같다. 

 

무엇이 단절점인가?

어떤 조건을 만족해야 단절점이 될 수 있을까?를 먼저 알아야한다고 생각한다. 

정의대로라면 단절점이란 그 정점과 그 정점에 해당된 모든 간선을 삭제했을 때 그래프가 2개 혹은 그 이상으로 나누어지는 정점이다.

 

직관적으로 생각해보면 어떤 점이 단절점이 될 수 있을까?  두 그래프를 이어주는 노드가 될 수 있겠다. 또한 어떠한 한 노드가 다른 상위노드로 이동할 때 반드시 거쳐야하는 정점정도로 생각할 수 있을 것이다. 예를 들면 다음과 같다. 

 

예제의 그래프를 그려 보겠다. 

예제의 그래프

다음과 같은 그래프가 존재할 때 7번 노드는 6번을 거치지 않고는 5번과 4번 노드로 이동할 수 없다. 1번 노드 또한 마찬가지이다. 7번 노드는 1번 노드를 거치지 않고는 4번과 5번 노드에 도달할 수 없다. 

 

반면에 2번 3번 4번 5번 노드의 경우 이 이 노드들이 사라져도 그래프 탐색에 문제가 없다. 2번이 사라져도 어떤 한 노드에서 시작해서 모든 그래프를 dfs로 탐색할 수 있고 5번이 사라지는 경우에도 어떠한 시작 노드로부터 모든 노드들을 dfs로 탐색할 수 있다. 

 

위의 그래프에선 따라서 2, 3, 4, 5번 노드는 단절점에 해당하지 않고 1번 6번 7번 노드가 단절점에 해당한다. 

 

그러면 단절점은 어떤 특징을 가지고 있을까?

 

단절점의 특징

위의 그래프를 dfs로 탐색한다면 어떠한 순서로 탐색이 될까? 

벡터로 인접리스트를 만든 후 탐색을 진행하기 때문에 사실 탐색되는 순서는 간선의 입력 순서에 의해 변할 수는 있다. 

하지만 예제에서의 입력순서라면 다음과 같이 탐색될 것이다. 

 

dfs에 의한 탐색 순서

단절점과 단절점이 아닌 경우를 나누어서 생각해보겠다. 

 

단절점의 경우

단절점인 6을 기준으로 생각해보자 6에서 dfs를 돌려 가장 작은 dist(자신의 dfs방문 순서)를 return한다고 했을 때 6에서 시작한 dfs는 다음 4개의 노드를 탐색할 수 있다. 하지만 그 노드들 중 어떠한 노드도 자신보다 전체 그래프에서 빠르거나 같게 탐색될 수 있는 정점이 존재하지 않는다. 

 

단절점이 아닌 경우를 살펴보겠다. 5번 노드의 경우 단절점에 해당하지 않는다. 

아닌 경우에는 위와 같이 5번 노드에서 시작하여 탐색할 수 있는 가장 빠른 탐색 순서는 1번 노드의 1에 해당한다. 

5번 노드는 3번째 탐색 순서에 해당하는데 자기부터 시작해서 탐색할 수 있는 노드가 자신보다 빨리 탐색될 수 있는 노드에 해당되니 이 점은 단절점에 해당되지 않는다. 

 

그렇다면 단절점을 위의 성질을 이용해서 어떻게 판단할 수 있을까?

 

바로 자신부터 시작해 dfs탐색을 시작할 때 return되는 가장 작은 수를 자신의 탐색 순서와 비교한다. 

이 때 return되는 가장 작은 수가 자신보다 크거나 같다면 이 정점으로부터 시작해 이 정점의 위에 해당하는 노드로 올라갈 수 있는 경로가 존재하지 않는다는 것을 의미한다. 따라서 이 점은 단절점에 해당한다. 

 

반면 해당 정점으로부터 dfs를 시작해 돌았을 때 return되는 수가 자신보다 작은 수라면 dfs시작 정점보다 더 빠르게 탐색되는 노드로 갈 수 있는 경로가 존재한다는 뜻이 된다. 따라서 이 점은 단절점에 해당하지 않는다. 

 

반면 한 가지 예외 케이스가 존재한다. 바로 루트의 경우이다. 

dfs의 특징상 어떤 특정한 노드를 시작점으로 잡고 출발할 수 밖에 없다. 이 dfs의 시작점이나 만약 노드가 전부 이어져있지 않고 애초부터 나누어진 두 개의 그래프로 시작했다면 root에 해당하는 노드는 2개가 될 것이다. 따라서 방문 체크를 해준 후 모든 정점을 dfs의 시작점으로 한 번은 간주해보면서 만약 1번 노드를 시작점으로 dfs를 수행했는데 5번 노드는 방문한적이 없다면 이 노드는 1번 노드가 포함된 그래프와는 다른 그래프에 해당하니 다시 root로 간주하며 dfs탐색을 돌아줘야한다. 

 

root의 경우는 자신보다 빨리 탐색될 수 있는 노드가 존재하지 않으므로 단순히 root의 자식이 2개 이상이라면 단절점에 해당한다. 

 

따라서 위의 내용을 바탕으로 구성한 코드는 다음과 같다. 

 

4. 코드

#pragma warning (disabld : 4996)
#include <cstdio>
#include <vector>
#include <algorithm>
#define MAX 10000
using namespace std;
int n,m,dist[MAX+1], cut[MAX+1], ans, d;
vector<vector<int>> v;
int dfs(int here, bool root) {
	dist[here] = ++d;
    int child = 0; // 만약 root에 해당한다면 자식 개수로 판단해줘야한다.
    int ret = dist[here];
    for(int there : dist[here]) {
    	// 인접리스트 탐색
        if(!dist[there]) {
        	//방문한 적이 없는 노드라면 이 노드를 시작으로 ret을 받는다.
            child++; // 자식 노드 ++
            int df = dfs(there, 0); //이미 부모가 존재하므로 root는 아니다. 
            if(!root && dist[here] <= df) cut[here] = 1; // 만약 루트가 아니면서 dfs의 리턴 값중 가장 작은 것이 자신의 탐색 순서보다 크거나 같다면 단절점이다.
            ret = min(ret, df); // 그 ret값 중 가장 작은 것과 비교해야한다.
        }
       	else ret = min(ret, dist[there]); // 방문한 적이 있다면 그 방문순서와 비교한다.
    }
    if(root && child > 1) cut[here] = 1; // 만약 루트면서 자식노드가 2개 이상이라면 단절점이다.
    
    return ret; // 리턴 값을 리턴한다.
}
int main() {
	scanf("%d %d", &n, &m);
	v.resize(n + 1);
	for (int i = 0; i < m; i++) {
		int s, e;
		scanf("%d %d", &s, &e);
		v[s].push_back(e);
		v[e].push_back(s); //양방향 그래프
	}
    
    for(int i=1; i <= n; i++) {
    	if(!dist[i]) dfs(i, 1); // 방문한 적이 없다면 root로 탐색 시작 
    }
	for (int i = 1; i <= n; i++) {
		if (cut[i]) ans++;
	}
	printf("%d\n", ans);

	for (int i = 1; i <= n; i++) {
		if (cut[i]) printf("%d ", i);
	}
	return 0;
}