BOJ 1733 : 등번호

문제 링크 : https://www.acmicpc.net/problem/1733

 

N명의 사람이 앞 뒤에 숫자가 적힌 유니폼을 갖고 있다.

각자 앞 또는 뒤에 적힌 숫자를 골라 N명의 사람이 고른 숫자가 겹치지 않게 하는 해를 출력하면 되는 문제다.

 

처음에 문제를 보자마자 든 생각은 이게 왜 플레1 이나 하지? 였다.

그냥 이분매칭인데, 단순한 이분매칭은 플레4~5 이기 때문이다. 하지만 N 제한이 100만인 것을 알고 납득했다.

 

혹시 새로운 이분매칭 알고리즘을 배워야만 하나? 하고 검색하니 Hopcroft - Karp 가 있긴 했다.

그래도 O(N 루트 N) 이라 시간초과 뜰 것 같아 다른 해법을 고민하기 시작했다.

 

약간의 관찰을 통해 그래프 탐색 느낌이 난다는 것을 알게 되었다.

예를 들어 1번 학생이 4를 선택했다면, 앞 뒤 중 4가 있는 학생을 찾아야 하기 때문이다.

그 학생은 4 이외의 수를 무조건 선택해야 하고, 그 수가 앞 뒤 중 있는 또 다른 학생으로 탐색을 이어간다.

 

또 눈에 들어오는 것은 한 학생당 숫자가 2개뿐이라는 것이다.

(x, y) 좌표평면도 순간 떠올랐지만, 위 문단과 연계해보면 두 숫자가 정점, 학생이 간선이라는 생각을 했다.

예를 들어 1번 학생이 4 10 이라면, 4 와 10을 잇는 간선이 곧 1번 학생이 된다는 것이다.

 

이렇게 만들어진 그래프에서 어떤 문제를 푸는 것일까?

각 간선은 자신의 양끝 정점 중 하나를 선택하는 것이다. 모든 간선이 겹치지 않게 정점을 선택하면 된다.

따라서 이 그래프에서 E > V 가 되면 해가 없다. 정점을 선택하지 못한 간선이 반드시 생기기 때문이다.

(여기서 E 는 간선 수, V 는 정점 수이다.)

 

그러므로 아래부터는 E ≤ V 라고 가정하고 서술한다.

여기서 자연스럽게 들었던 생각이, 말단 노드, 즉 차수가 1인 노드과 연관된 선택이 한 가지라는 것이다.

위 그림에서 보면 X는 간선 a 를 선택해야만 한다. X와 a는 이제 없다고 봐도 무방하다.

이제는 Y가 차수가 1이 되어 Y는 b를 선택해야만 하고, Y와 b는 사라진다.

Z는 차수가 1보다 크기 때문에 아직은 더 지켜봐야 한다. 

위상정렬과 꽤 진행이 유사하다는 것을 볼 수 있다.

 

이런식으로 차수가 1인 노드들을 없애면 차수가 2 이상인 노드들만 남게 된다.

조금만 생각해보면 E = V 일 수 밖에 없다.

기본적으로 E ≤ V 라고 가정했는데, 모든 노드의 차수가 2이상이기에 E ≥ V 이기 때문이다.

 

핵심 : V = E 이고 모든 노드의 차수가 2 이상이면 서로 독립적인 사이클들로만 구성될 수 밖에 없다.

우리는 위 상황을 강제로 만든 후이기 때문에, 아직 선택 안된 노드부터 탐색해 사이클을 찾으면 된다.

사이클은 노드 수 = 정점 수 이므로 간선들이 겹치지 않게 항상 정점을 선택할 수 있다.

따라서 우리는 O(N) 으로 문제를 해결하게 된다.