배타적 접근 2

예전 대회에서 상호 배제 프로토콜을 공부한 여러분은 이제 더 어려운 문제를 마주한다. 여러 프로세스가 동시에 실행되는 대규모 기업용 시스템을 운영하고 있다. 이 시스템에는 데이터베이스, 메시지 큐 등 여러 개의 자원이 있다. 각 프로세스는 한 번에 정확히 두 개의 자원을 사용한다. 예를 들어 어떤 프로세스는 특정 데이터베이스에서 작업을 꺼내 메시지 큐에 넣고, 다른 프로세스는 그 큐에서 작업을 꺼내 수행한 뒤 결과를 또 다른 큐에 넣는다.

모든 자원은 상호 배제 잠금(lock)으로 동시 접근이 보호된다. 자원을 사용하려면 프로세스는 그 자원의 잠금을 획득하고, 작업을 수행한 뒤, 잠금을 해제한다. 두 프로세스가 같은 잠금을 동시에 보유할 수는 없으므로(상호 배제), 어떤 잠금을 획득하려는 프로세스는 그 잠금을 다른 프로세스가 이미 보유하고 있으면 기다려야 한다.

자원 P와 Q를 사용하는 프로세스의 주 반복문은 다음과 같다.

loop forever  DoSomeNonCriticalWork()  P.lock()  Q.lock()  WorkWithResourcesPandQ()  Q.unlock()  P.unlock()end loop

두 잠금을 획득하는 순서가 중요하다. 프로세스 c가 잠금 P를 획득한 뒤 잠금 Q를 기다리고 있다고 하자. 그러면 Q는 다른 프로세스 d가 보유하고 있다. 만약 d가 (기다리지 않고) 작업 중이라면 길이 1의 대기 사슬이 있다고 한다. d가 Q를 보유한 채 작업 중인 프로세스 e가 보유한 다른 잠금 R을 기다리고 있다면 대기 사슬의 길이는 2이며, 이런 식으로 이어진다. 사슬 안의 어떤 프로세스가 이미 프로세스 c가 보유한 잠금 P를 기다린다면, 대기 사슬은 무한히 길어지고 시스템은 교착 상태에 빠진다.

우리는 모든 프로세스가 첫 번째 잠금을 보유한 채 두 번째 잠금을 기다리는 교대(alternating) 대기 사슬에만 관심이 있다. 형식적으로 정의하면 다음과 같다.

길이 n (n >= 0)의 교대 대기 사슬은 자원 R0, R1, ..., R(n+1)과 서로 다른 프로세스 c0, c1, ..., cn이 번갈아 나오는 수열 R0 c0 R1 c1 ... Rn cn R(n+1)이며, 각 프로세스 ci는 Ri와 R(i+1)의 잠금을 이 순서대로 획득한다. R0 = R(n+1)이면 이 사슬은 교착 상태이다.

각 프로세스가 사용하는 두 자원이 주어진다. 시스템이 절대 교착 상태에 빠지지 않으면서 가능한 교대 대기 사슬의 최대 길이가 가장 작아지도록, 각 프로세스가 두 잠금을 획득하는 순서를 정할 수 있다. 이때 얻을 수 있는 최대 길이의 최솟값을 구하여라.

첫째 줄에 프로세스의 수 n (1 <= n <= 100)이 주어진다.

다음 n개의 줄에는 각 프로세스가 사용하는 서로 다른 두 자원이 공백으로 구분되어 주어진다. 모든 자원은 L부터 Z까지의 대문자이므로, 서로 다른 자원은 최대 15개이다.

정수 m 하나를 출력한다. m은 시스템이 교착 상태에 빠지지 않도록 각 프로세스의 잠금 획득 순서를 정하는 모든 방법에 대해 최소화한, 가장 긴 교대 대기 사슬 길이의 최솟값이다.

이 최솟값을 달성하는 교착 없는 순서 배정은 여러 가지일 수 있으며, 요구되는 것은 그 값 m뿐이다.