Baekjoon(백준) 14866번 - 산만한 고양이

백준 사이트의 14866번.
문제 제목 : 산만한 고양이
백준 14866

한국정보올림피아드 (KOI) 2017년도 중등부 4번 문제였다.
예전에는 한국정보올림피아드가 국가에서 주관하는 엄청 큰 대회이면서 공신력과 파워(?)를 가진 대회였는데… 흐지부지 되며 사실상 없어진 것이 아쉬울 따름이다. 초등부나 중등부 또는 고등부 학생들에게 국가에서 주도하는 대회에서 너무 선행 지식을 요구한다는 컴플레인과 (대학 컴공과에서 배우는 그래프 이론이나 그런 알고리즘 등등) 마지막 대회 때 문제 오류 + 채점 서버 장비 오류로 인해 엄청난 불만이 폭주하면서 국가 주관에서 다른 기관으로 주관이 넘어갔다. 그래도 다른 분야의 올림피아드 (KMO 등) 도 정부가 주관하지 않는데 꾸준히 실력 좋은 학생들이 경쟁하고 유명한 걸 보면 정보올림피아드도 그런 수순을 밟을 줄 알았지만 최근 소식을 들어보니 어찌저찌 운영되고 있기는 하나 많이 약해졌고 운영도 깔끔하게 안된다고 들었다.
개인적으로는 어차피 그 당시에도 참여하고 싶은 사람만 참여하는 대회이니 선행 지식을 이용한 문제를 내도 그게 왜 문제가 되었는지 모르겠다. 하지만, 마지막 대회에서 문제 오류, 채점 서버 오류는 명백한 관리 부실이고 아쉽게 생각된다. 어쩌면 내가 프로그래밍을 시작하고 순수한 호기심과 열정으로 가장 열심히 프로그래밍을 공부했던, 그 중심에 있던 대회여서 내심 뿌듯함과 그 대회에 대한 애정이 있기에 더욱 아쉬움이 느껴진다.

무튼 예전에는 다 알았던 내용들을 싹 까먹어 버리는 바람에 문제를 어떻게 풀지 오랜 시간 고민했으나 마땅한 답을 찾지 못했다. 그래서 예전에 공부했던 것 + 추가적으로 새로 공부를 하고 문제의 해설을 찾아 또 다시 오랜 시간 연구한 끝에 완전히 해답을 이해하고 만점을 받을 수 있었다. (그 중간에 다른 일도 있었고, 운전면허 도로주행 시험을 하느라 더 늦어졌다) 중등부 문제이지만 마지막 문제인 4번이라서 매우매우매우 어렵다. 사실 이걸 중학생들에게 만점을 받으라고 하기에는 대부분 무리가 있지 않나 싶다. 물론… 그렇지 않은 미친 실력을 겸비한 중학생들도 그 당시 있었다. 역시 대단하다 K-중딩!

문제 해석

각설하고 문제는 주저리주저리 많이 써있는데 해석해보면 간단하다. 입력으로 무방향 그래프 가 주어진다. 여기서 하나의 vertex만 삭제하여 그래프에 cycle이 존재하지 않도록 할 수 있는가를 묻는 문제이다. 그러한 vertex가 없다면 0, 그러한 vertex가 여러개라면 그 index(번호)를 모두 더해서 출력하면 된다.

풀이 전략

중요한 fact가 하나 있다.

무방향 그래프에서 cycle이 존재한다는 것은 그 그래프의 dfs tree에서 back edge 가 존재한다는 말과 동치이다.

상당히 중요한 사실인데 이 사실을 까먹고 있었다… (머쓱;;)
비슷하게 방향 그래프에서도 back edge를 사용해서 cycle의 유무와 개수 (back edge의 개수가 곧 cycle의 갯수) 를 알아낼 수 있다. 이론을 살짝 정리하고 넘어가보자. (‘알고리즘 문제해결 전략’ 책의 내용을 참고했다)

DFS와 간선(edge)의 분류

DFS(깊이 우선 탐색)를 실행하면 그래프의 모든 간선을 한 번씩은 만나게 된다. 보통은 DFS를 할 때 이미 방문한 정점은 무시하고 방문하지 않은 새로운 정점만 탐색을 하게 되는데, 이 때 이미 방문한 정점에 대해서도 정보를 처리해주면 그래프의 구조에 대해 더 자세하게 알아낼 수 있다. 어떤 한 정점에서 시작하여 DFS를 통해 형성되는 tree를 우리는 ‘DFS spanning tree’ 라 한다. i번 vertex에서 시작하여 DFS를 실행한 tree는 i를 root로 가지는 DFS spanning tree가 되는 것이다. 그래서 그래프 전체에 대해서 DFS spanning tree를 형성하게 되면 그래프의 모든 edge를 4가지로 분류한다.

1. tree edge : spanning tree에 포함된 edge.
2. forward edge : spanning tree의 ancestor에서 child로 연결되지만 tree edge가 아닌 것
3. back edge : spanning tree의 child에서 ancestor로 연결되는 edge
4. cross edge : 그 이외의 나머지 edge. ancestor와 child의 관계가 아닌 vertex 간에 연결된 edge

spanning tree는 한 그래프에서 여러가지가 나올 수 있기 때문에 각 edge는 그 분류가 달라질 수 있다. 또한, 본 문제에서 다루는 무향 그래프는 forward edge는 back edge와 같고 (구분이 없고), cross edge는 존재하지 않는다.

back edge를 이용한 풀이 방법

그럼 우리는 처음에 그래프의 연결관계를 입력받은 후 DFS 를 해서 DFS spanning tree를 형성함과 동시에 그 그래프에서 back edge에 관한 정보를 알아내면 된다. back edge에 관한 정보를 알아내면 다음과 같은 vertex (vertex의 index는 $i$라 하겠다) 제외하고 나머지 모든 vertex의 index를 더해주면 된다. (즉, 아래에 나와 있는 것은 $i$ vertex를 없애도 여전히 cycle이 존재하는 경우를 의미)

1. $i$의 child를 root로 하는 sub-tree내에 back edge가 있을 때
2. $i$의 child를 root로 하는 sub-tree의 vertex와 $i$의 ancestor 사이에 2개 이상의 back edge가 있을 때
3. $i$를 root로 하는 sub-tree 이외의 곳에 back edge가 있을 때

위의 사진이 1번 case에 대한 예시를 나타낸 figure이고, 아래 사진은 2번 case에 대한 figure이다. (색칠된 vertex가 $i$ 이다)

구현

DFS 를 실행하면서 그래프의 back edge에 관한 정보를 알아낸다고 했는데 구체적으로는 다음과 같은 3가지를 알아내면 된다.

1. cbe[i] : completely included back edge, i를 root로 하는 sub-tree의 완전히 내부에 속해있는 back edge
2. ibe[i] : included back edge, i를 root로 하는 sub-tree에 ‘걸쳐있는’ (back edge 중 한쪽이라도 sub-tree에 속한) back edge
3. pbe[i] : parent connected back edge, i를 root로 하는 sub-tree의 vertex와 i의 parent를 연결하는 back edge

헷갈리면 안되는 것이 이 글에서 i의 parent는 i의 바로 한단계 위에 연결된 vertex를 의미하고 i의 ancestor는 i의 parent 뿐만 아니라 parent의 윗단계로 연결된 모든 vertex를 포함하는 의미이다. 아무튼 이 세가지 정보를 이용하면 위의 풀이 방법에서 언급했던 3가지의 case를 모두 구별해낼 수 있다. DFS 를 하면서 트리의 depth 정보를 이용하여 tree edge인지 back edge 인지 구분하고 세가지 정보를 갱신하게 되는데 그 코드가 다음과 같다.

int dfs_search(int parent, int cur)
{
	for(int i = 0; i < graph[cur].size(); i++) {
		int next = graph[cur][i];

		if(next == parent) continue;
		else if(depth[next] == 0) {
			//tree edge
			tree[cur].push_back(next);
			depth[next] = depth[cur] + 1;	
			
			int temp = cbe[cur];

			dfs_search(cur, next);

			pbe[next] = cbe[cur] - temp;
			cbe[cur] += cbe[next];
			ibe[cur] += ibe[next];
		}
		else if(depth[next] < depth[cur]) {
			//back edge	
			ibe[cur]++;	
			cbe[next]++;
		}
	}	

	return 0;	
}

나머지 갱신하는 부분이나 여러가지 부분은 이해가 갈 것으로 생각한다. (적어도 나는 그랬다) 내가 가장 이해가 안됐던 부분은

int temp = cbe[cur];
dfs_search(cur, next);
pbe[next] = cbe[cur] - temp;

이 부분 이었다. 이해한대로 간략하게 설명을 하자면 (내가 틀렸을수도…)
cur의 child는 여러 개가 있을 수 있다. 따라서, 이미 next 전에 앞의 child 들에 의해 cbe[cur] 가 일부 계산된 값이 있을 수 있다. 이를 temp에 저장한 후 next로 넘어가 DFS를 하는 재귀함수를 호출한다. 저 함수가 호출된 뒤에는 밑에 child들에 대한 search가 끝나기 전까지 cur에 대해서는 다음 줄로 코드가 넘어가지 않는다. 즉, child들에 대한 search가 이루어질 때 cbe[cur] 가 1씩 더해지는 경우는 child에서 cur로 연결되는 back edge인 경우 밖에 없다.

else if(depth[next] < depth[cur]) {
 //back edge	
	ibe[cur]++;	
	cbe[next]++;
}

이 코드에서 cbe[next]++; 바로 이부분으로 인해 cbe[cur] 가 1씩 더해지는 것이다. (child 중에서 back edge로 연결되는 경우를 check 하는 코드 이므로 코드에서의 next가 곧 우리가 얘기하는 상황에서의 cur가 되는 것이다)
따라서, dfs_search(cur, next); 부분에서 cbe[cur]의 변화량이 곧 pbe[next] (next의 parent로 연결되는, 즉 cur로 연결되는 back edge) 가 된다.
아무튼, 꽤 많은 고민과 탐구를 요구하는 문제인 것 같다. 상당히 어려운 문제였다.
자세한 코드와 솔루션은 github에 있다.

baekjoon 14866 solution code