정삼각형 도미노

시간 제한15초메모리 제한128 MB

요약

1부터 6까지의 눈이 적힌 정삼각형 도미노를 최대 6개 줄 때, 삼각 격자 위에 연결된 부분집합을 배치해 맞닿은 끝의 수가 같은 공유 변의 개수를 최대로 만든다.

난이도: 어려움10점 중 8점
유형: 백트래킹, 기하, 그래프, 시뮬레이션
정답자: 아직 제출이 없습니다

문제

보통의 도미노는 세로가 가로보다 두 배 긴 직사각형 타일이며, 두 정사각형 끝면에는 각각 $1$ 부터 $6$ 까지의 수가 눈금으로 표시되어 있습니다. 도미노 놀이는 서로 맞닿는 끝면의 수가 같도록 타일을 이어 놓는 방식으로 진행됩니다.

이번에는 도미노를 정삼각형으로 만들어 본다고 합시다.

정삼각형 도미노는 두 개의 정삼각형을 한 변끼리 붙여 만든 사각형(마름모)입니다. 마찬가지로 양쪽 끝의 삼각형에는 각각 $1$ 부터 $6$ 까지의 수가 적혀 있습니다. 두 정삼각형 도미노는 맞닿는 변의 양쪽 삼각형 끝에 적힌 수가 서로 같을 때에만 나란히 놓을 수 있으며, 어떤 도미노도 다른 도미노와 겹칠 수 없습니다. 첫 번째 도미노를 놓은 뒤에는, 새로 놓는 도미노를 반드시 이미 놓인 도미노 중 적어도 하나와 변을 맞대도록 놓아야 합니다. 즉, 놓인 도미노들은 항상 하나로 이어진 덩어리를 이루어야 하며, 서로 떨어진 두 개 이상의 덩어리는 올바른 배치가 아닙니다. 예를 들어 정삼각형 도미노를 다음과 같이 놓을 수 있습니다.

두 도미노가 맞닿아 공유하는 변 하나마다 $1$ 점을 얻습니다. 주어진 정삼각형 도미노 집합에 대하여, 올바른 배치로 얻을 수 있는 최고 점수를 구하세요. 집합의 모든 도미노를 반드시 사용할 필요는 없습니다.

입력

입력은 여러 개의 테스트 케이스로 이루어집니다. 각 테스트 케이스의 첫 줄에는 정삼각형 도미노의 개수를 나타내는 정수 $N$ ( $1 \le N \le 6$ )이 주어집니다. 이어지는 $N$ 개의 줄에는 각각 $1$ 이상 $6$ 이하의 두 정수가 주어지며, 이는 한 도미노에 적힌 두 눈금 값을 나타냅니다. 입력의 끝에는 $0$ 하나만 있는 줄이 주어지며, 이 줄은 처리하지 않습니다.

출력

각 테스트 케이스마다 주어진 정삼각형 도미노 집합으로 얻을 수 있는 최고 배치 점수를 한 줄에 출력합니다. 어떤 도미노도 다른 도미노와 나란히 놓을 수 없어 점수를 얻는 배치가 없다면 $0$ 을 출력합니다.

예제5

예제 1

입력

예상 출력

4
0
1

예제 2
입력
```
1
3 4
0
```
예상 출력
```
0
```
예제 3
입력
```
2
1 1
1 1
0
```
예상 출력
```
1
```
예제 4
입력
```
2
5 6
2 1
0
```
예상 출력
```
0
```
예제 5
입력
```
3
6 6
6 6
6 6
0
```
예상 출력
```
3
```