색칠된 정육면체

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

요약
최대 4개의 색칠된 정육면체가 주어질 때, 회전으로 서로 같아지도록 만드는 데 필요한 최소 면 재도색 수를 구합니다.
난이도

보통10점 중 6점

유형
완전 탐색, 시뮬레이션, 조합론
정답자
아직 제출이 없습니다

문제

크기가 모두 같은 정육면체 여러 개가 있다. 각 정육면체의 여섯 면은 각각 한 가지 색으로 칠해져 있으며, 한 정육면체의 서로 다른 두 면은 같은 색일 수도, 다른 색일 수도 있다.

한 정육면체를 공간에서 회전시켜 면 하나하나까지 다른 정육면체와 완전히 똑같아 보이게 만들 수 있으면, 두 정육면체는 같은 색 배열이라고 한다. 정육면체를 뒤집는(거울에 비추는) 것은 허용되지 않고 강체 회전만 허용되므로, 어떤 정육면체와 그 거울상이 반드시 같은 색 배열인 것은 아니다. 정육면체 집합에 속한 모든 정육면체 쌍이 서로 같은 색 배열이면, 그 집합을 같은 색 배열이라고 한다.

임의의 정육면체의 임의의 면을 원하는 색으로 다시 칠할 수 있다. 정육면체 집합이 주어질 때, 집합 전체를 같은 색 배열로 만들기 위해 다시 칠해야 하는 면의 최소 개수를 구하여라.

입력

입력은 여러 개의 데이터셋으로 이루어진다. 각 데이터셋의 첫 줄에는 정육면체의 개수 nn (1≤n≤41 \le n \le 4)이 주어지고, 이어서 정육면체마다 한 줄씩 총 nn개의 줄이 주어진다.

각 정육면체 줄에는 여섯 면의 색이 면 번호 1,2,3,4,5,61, 2, 3, 4, 5, 6 순서대로 공백 하나로 구분되어 주어진다. 면의 배치는 11번과 66번, 22번과 55번, 33번과 44번이 각각 서로 마주 보도록 되어 있으며, 모든 정육면체가 같은 면 번호 규칙을 따른다.

색 이름은 하이픈(-)으로 이어진 하나 이상의 단어로 이루어지고, 각 단어는 하나 이상의 영어 소문자로 이루어진다. 색 이름의 길이는 하이픈을 포함하여 최대 2424자이다.

입력의 끝은 00 하나만 있는 줄로 표시되며, 이 줄은 데이터셋이 아니다.

출력

각 데이터셋에 대해, 정육면체 집합을 같은 색 배열로 만들기 위해 다시 칠해야 하는 면의 최소 개수를 한 줄에 출력한다.

예제5

  1. 예제 1

    입력
    3
scarlet green blue yellow magenta cyan
blue pink green magenta cyan lemon
purple red blue yellow cyan green
2
red green blue yellow magenta cyan
cyan green blue yellow magenta red
2
red green gray gray magenta cyan
cyan green gray gray magenta red
2
red green blue yellow magenta cyan
magenta red blue yellow cyan green
3
red green blue yellow magenta cyan
cyan green blue yellow magenta red
magenta red blue yellow cyan green
3
blue green green green green blue
green blue blue green green green
green green green green green sea-green
3
red yellow red yellow red yellow
red red yellow yellow red yellow
red red red red red red
4
violet violet salmon salmon salmon salmon
violet salmon salmon salmon salmon violet
violet violet salmon salmon violet violet
violet violet violet violet salmon salmon
1
red green blue yellow magenta cyan
4
magenta pink red scarlet vermilion wine-red
aquamarine blue cyan indigo sky-blue turquoise-blue
blond cream chrome-yellow lemon olive yellow
chrome-green emerald-green green olive vilidian sky-blue
0
    예상 출력
    4
2
0
0
2
3
4
4
0
16

  2. 예제 2

    입력
    2
red green blue yellow magenta cyan
red green blue yellow magenta cyan
0
    예상 출력
    0

  3. 예제 3

    입력
    2
red red red red red red
blue blue blue blue blue blue
0
    예상 출력
    6

  4. 예제 4

    입력
    4
aaa aaa aaa aaa aaa aaa
bbb bbb bbb bbb bbb bbb
ccc ccc ccc ccc ccc ccc
ddd ddd ddd ddd ddd ddd
0
    예상 출력
    18

  5. 예제 5

    입력
    4
aa ab ac ad ae af
ba bb bc bd be bf
ca cb cc cd ce cf
da db dc dd de df
0
    예상 출력
    18