레오나르도 다 빈치의 코덱스 아틀란티쿠스 에는 최초로 설계한 꽤 정교한 낙하산이 설명되어 있는데,

이 다 빈치의 낙하산은 피라미드 모양의 나무 구조를 통해 열리는 우산모양의 리넨 옷감으로 설계되어있다.

고리 구조

스카이다이버 아드리안 니콜라스는 500년 이상 오래된 다 빈치의 디자인을 시험해보았다.

이를 위해, 사람의 몸을 다 빈치의 낙하산에 묶기 위한 최신식 초경량 구조를 사용하였다.

우리는 리넨 옷감에도 걸 수 있는 고리 구조를 사용하고자 한다. 각각의 고리는 유연하고 강한 소재로 만들어졌다.

모든 고리들은 열고 닫을 수 있으므로, 다른 고리들과 쉽게 연결될 수 있다. 체인은 고리 구조의 특별한 형태를 말한다.

아래에 있는 그림처럼, 각각의 고리들이 (최대 두 개의) 인접한 고리들과 차례대로 연결되어 있고,

시작과 끝이 있는 고리 구조는 체인이 된다. (시작과 끝에 있는 고리들은 각각 최대 하나의 다른 고리들과 연결된다.)

특히, 고리 하나도 마찬가지로 체인이다.

하나의 고리가 세 개 이상의 다른 고리들과 연결된 고리 구조의 형태도 당연히 가능하다.

이러한 고리 구조에서, 어떤 하나의 고리를 열어서 없앤 후에 남은 다른 고리들이 모두 체인의 형태를 만들 때 (혹은 고리가 하나도 남지 않았을 때),

그 고리를 중요한 고리라고 한다. 다시 말해, 중요한 고리를 제거하면, 체인만 남게 된다.

예제

다음의 그림과 같이, 0번부터 6번까지 번호가 매겨진 7개의 고리를 생각해보자.

이 고리 구조에는 2개의 중요한 고리가 있다.

그 중 하나는 2번인데, 이 고리를 없애면 남은 고리들이 [1], [0, 5, 3, 4], 그리고 [6]의 체인이 된다.

다른 하나는 3번인데, 이 고리를 없애면 남은 고리들이 [1, 2, 0, 5], [4], 그리고 [6]의 체인이 된다.

만약 그 이외의 다른 고리들을 없애면, 체인이 아닌 것이 남아있게 된다.

예를 들어, 5번 고리를 없애면 [6]은 체인이 되지만, 0번, 1번, 2번, 3번, 그리고 4번 고리로 만들어진 고리 구조는 체인이 아니다.

해야할 일

여러분이 할 일은 입력으로 주어지는 고리 구조에서, 중요한 고리의 개수를 출력하는 프로그램을 작성하는 것이다.

낙하산 고리들(Parachute rings) timer 5초 memory 64MB

낙하산 고리들(Parachute rings) 5초 64MB