BOJ 19544 : 함수 복원

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

 

함수의 값이 f(x) = y 라면, x -> y 로 이어주는 방향그래프의 가짓수를 구하는 문제다.

우선 중요한 점은 함수기 때문에, 모든 노드의 outdegree == 1 이라는 사실이다. 

indegree 는 얼마든지 커질 수 있고 0 일 수도 있지만, outdegree 만큼은 다 1 이어야 한다.

 

이 문제의 아이디어는 BOJ 6991 계통트리와 유사하게 떠올렸다. (계통트리 풀이)

예제를 보니 갈 수 있는 정점들이 완전히 일치하는 노드들이 나왔다.

계통트리에서는 이런 노드들이 같은 부모를 공유한다는 관찰을 해야 했다.

조금만 생각해보면, 이 문제에서는 이 노드들은 같은 사이클 속에 있다는 것을 알게 된다.

 

예제 1을 예시로 보자.

 

6
1 1 1 1 0 0
0 1 1 1 0 0
0 1 1 1 0 0
0 1 1 1 0 0
1 1 1 1 1 0
0 0 0 0 0 1

 

위에서 볼 수 있 듯이 2, 3, 4 행이 0 1 1 1 0 0 으로 완전히 일치한다.

즉 2, 3, 4 는 셋이서 맞물리는 사이클을 형성하고 있다는 것이다.

 

그렇다면, 한 사이클에 대하여 그 배열 방법에는 몇 가지가 존재할까?

사이클은 곧 원 모양이므로, 원탁에 노드들을 배치하는 가짓수, 즉 원순열과 같다.

따라서, 답에는 기본적으로 (각 사이클들의 원소 수 - 1) ! 들이 곱해진다.

위 예시의 2, 3, 4 는 (2 3 4) 와 (2 4 3) 두 가지가 있을 것이다. 즉, (3-1) ! = 2 가지다.

 

여기서 하나 더 관찰을 해야 한다.

이런 식으로 모든 사이클을 찾게 되면, 우리는 DAG, 즉 사이클이 없는 방향 그래프를 얻게 된다.

이게 다가 아니고, 사이클은 절대 다음 노드가 없다는 것이다.

불가능한 case

즉 위 같은 그림이 불가능하다는 것이다. 왜 그럴까?

첫 문단에서 언급했듯, 함수를 바탕으로 형성된 방향그래프기에, 모든 노드의 outdegree 는 1이다.

위 그림처럼 되면 노드 3 의 outdegree 가 2 가 되기에, 불가능하다.

이제 알 수 있는 것은, 위상정렬을 하게 된다면 사이클들은 항상 마지막 순서 (더 이상 확장이 안됨) 다.

 

그럼 우리가 알 수 있다는 것은 임의의 사이클은 그 전의 원소들만 존재한다는 것이고,

그 전의 원소들도 사이클이 될 수 없다. (사이클 다음 원소는 존재할 수 없기 때문)

 

즉, 임의의 사이클에 대하여 그 사이클 전의 원소는 무조건 단일 원소라는 것이다.

잘 이해가 되지 않는다면 아래 그림을 보면 된다.

위 그림처럼, 사이클 전의 원소들은 단일 체인으로 구성될 수 밖에 없다.

그럼 여기서 또 가짓수가 나뉜다.

5 입장에서는 1, 3, 7 중 어느 것에 연결되어도 상관이 없다. 즉 5 입장에서는 선택지가 3개다.

그렇기 때문에, 답에 추가적으로 3이 곱해지게 된다.

 

정리하자면 아래와 같다.

1. 같은 사이클들에 속하는 원소들을 찾는다. (해시, 맵 등을 이용)

( 입력된 배열에서 I 번째 행과 J 번째 행이 완전히 같다면 I 와 J 는 같은 사이클 )

 

2. 사이클들의 크기들을 각각 구한 후, (한 사이클의 크기 - 1) ! 들을 전부 곱한다.

( 사이클 내에서 회전하는 총 가짓수 )

 

3. 각 사이클에 대하여, 그 직전의 노드가 존재하는지 살펴본다.

이는 입력된 배열에서 1이 딱 하나 더 많으면 그 원소가 직전 노드라는 사실로 찾을 수 있다.

( 예 : 위 그림에서 5 는 1, 3, 5, 7 을 가고, 1 은 1, 3, 7 을 간다. 5가 갈 수 있는 곳이 딱 하나 더 많다. )

만약 그런 노드가 없으면 사이클 직전 노드가 없으므로 넘어가고,

있다면 그 노드 입장에서는 사이클의 노드들을 아무거나 선택할 수 있으므로,

답에다가 (그 사이클의 크기) 를 추가적으로 곱해준다.

 

좋은 문제라고 생각한다.