이상한 열쇠
시간 제한2초메모리 제한512 MB
단위 축 평행 막대로 이루어진 3차원 경로들의 집합으로 주어진 두 열쇠 설명이 회전과 평행 이동으로 같은 모양인지 판정한다.
문제
쓰쿠바 교수는 매우 이상한 모양의 황금 열쇠로 여는 신비한 보석함을 발명했다. 열쇠는 끝과 끝이 이어진 금막대기로 이루어져 있다. 모든 금막대기는 길이가 같고, 3차원 공간의 세 직교축, 즉 x축, y축, z축 중 하나에 평행하게 놓인다.
보석함의 잠금 장치는 정말 신비롭지만, 열쇠의 모양은 알려져 있다. 보석함의 열쇠를 식별하기 위해 그는 열쇠 모양을 기술하는 방법을 제시했다.
기술은 열쇠의 모양을 완전히 결정하는 연결된 경로의 목록을 나타낸다. 열쇠의 금막대기는 경로를 따라 배치되고 끝과 끝이 이어진다. 첫 번째 경로를 제외한 각 경로는 앞서 정의된 경로 위에 있는 금막대기의 끝점에서 시작해야 한다. 각 경로는 여섯 기호(+x, -x, +y, -y, +z, -z) 또는 양의 정수인 원소의 나열로 표현된다. 각 기호는 경로를 따라 한 끝점에서 금막대기의 다른 끝점으로 가는 방향을 나타낸다. 모든 금막대기는 세 직교축 중 하나에 평행하므로 여섯 기호로 방향을 나타내기에 충분하다. 경로의 기술에는 방향이 있지만 금막대기 자체에는 방향이 없다.
금막대기의 끝점에는 양의 정수인 레이블을 붙일 수 있다. 레이블이 붙은 점은 다른 경로의 시작점으로 참조될 수 있다. 열쇠 기술에서 양의 정수가 처음 나타나면 그 점의 레이블을 정의하고, 같은 양의 정수가 그 뒤에 나타나면 그 점에서 새 경로가 시작됨을 나타낸다.
13개의 금막대기로 이루어진 열쇠의 예가 그림 1에 나와 있다.
그림 1
다음과 같은 줄의 나열
19
1 +x 1 +y +z 3 +z
3 +y -z +x +y -z -x +z 2 +z
2 +y
은 그림 1의 열쇠를 기술한 것이다. 기술에서 줄바꿈은 공백 문자와 같은 역할을 하므로, "19 1 +x 1 +y +z 3 +z 3 +y -z +x +y -z -x +z 2 +z 2 +y"는 같은 의미를 가진다.
이 기술의 의미는 아주 간단하다. 첫 번째 정수 "19"는 이 기술에 이어지는 원소의 개수를 나타낸다. 각 원소는 여섯 기호 중 하나 또는 양의 정수이다.
둘째 줄 맨 앞의 정수 "1"은 첫 번째 경로의 시작점에 붙은 레이블이다. 일반성을 잃지 않고 첫 번째 경로의 시작점을 원점, 즉 (0,0,0)으로 두고 각 금막대기의 길이를 1로 가정할 수 있다. 다음 원소 "+x"는 첫 번째 금막대기가 x축에 평행함을 나타내므로 금막대기의 다른 끝점은 (1,0,0)에 있다. 이 두 원소 "1"과 "+x"는 금막대기 하나로 이루어진 첫 번째 경로를 나타낸다. 기술의 둘째 줄 세 번째 원소인 양의 정수 "1"은 레이블 "1"이 붙은 점, 즉 원점 (0,0,0)이 새 경로의 시작점임을 나타낸다. 이어지는 원소 "+y", "+z", "3", "+z"는 금막대기 세 개로 이루어진 두 번째 경로를 나타낸다. 여기서 "3"은 처음 나타나므로 좌표 (0,1,1)인 점에 레이블 "3"이 붙는다. 셋째 줄 맨 앞의 "3"은 세 번째 경로의 시작을 나타내는 식이다. 결국 네 개의 경로가 있고, 이것이 그림 1의 열쇠 모양을 완전히 결정한다.
열쇠 모양을 덮는 경로의 집합은 여러 가지가 될 수 있으므로 같은 열쇠를 기술하는 방법도 여러 가지이다. 예를 들어 다음과 같은 줄의 나열
19
1 +x 1 +y +z 3 +y -z +x +y -z -x +z 2 +y
3 +z
2 +z
은 금막대기가 같은 방식으로 놓이므로 그림 1의 열쇠를 기술한 또 다른 방법이다.
게다가 열쇠를 x축, y축, z축을 중심으로 90도씩 여러 번 회전시키거나 평행 이동시킬 수 있다. 회전과 평행 이동을 어떻게 조합해도 열쇠의 모양은 바뀌지 않으므로, 회전하고 이동한 열쇠를 기술한 것도 원래 열쇠와 같은 모양을 나타낸다. 예를 들어 다음과 같은 나열
17
+y 1 +y -z +x
1 +z +y +x +z +y -x -y 2 -y
2 +z
은 그림 1과 같은 열쇠를 나타내는 그림 2의 열쇠를 기술한 것이다. 실제로 두 열쇠는 x축을 중심으로 한 회전과 평행 이동으로 합동이다.
그림 2
주어진 두 기술이 같은 열쇠를 정의하는지 판정하는 프로그램을 작성하라.
경로가 순환을 이룰 수도 있다. 예를 들어 "4 +x +y -x -y"와 "6 1 +x 1 +y +x -y"는 올바른 기술이다. 그러나 두 개 이상의 금막대기가 같은 위치에 놓여서는 안 된다. 예를 들어 열쇠 기술 "2 +x -x"와 "7 1 +x 1 +y +x -y -x"는 올바르지 않다.
입력
입력은 열쇠 기술의 쌍의 나열이고, 마지막에 입력의 끝을 나타내는 0이 온다. p쌍의 열쇠 기술에 대해 입력은 다음 형식으로 주어진다.
key-description1-a
key-description1-b
key-description2-a
key-description2-b
...
key-descriptionp-a
key-descriptionp-b
0
각 열쇠 기술(key-description)은 다음 형식이다.
n e1 e2 ... ek ... en
양의 정수 n은 이어지는 원소 e1, ..., en의 개수를 나타낸다. 원소들은 하나 이상의 공백 문자나 줄바꿈으로 구분된다. 각 원소 ek는 여섯 기호(+x, -x, +y, -y, +z, -z) 중 하나 또는 양의 정수이다.
각 레이블은 51 미만의 양의 정수이고, 열쇠 기술 하나에 들어 있는 원소의 개수는 301 미만이며, 한 줄의 문자 수는 80 미만이라고 가정할 수 있다. 주어지는 열쇠 기술은 올바르고 금막대기를 하나 이상 포함한다고도 가정할 수 있다.
출력
출력 줄의 수는 입력으로 주어진 열쇠 기술 쌍의 수와 같아야 한다. 각 줄에는 두 열쇠 기술이 같은 열쇠를 나타내면 "SAME", 다르면 "DIFFERENT"를 출력한다. 글자는 모두 대문자여야 한다.