모눈종이에 다각형을 그리려고 한다. 그리는 방법은 모양수열로 표시된다. 모양수열은 1과 4사이의 숫자가 연속되어 나열된 것으로 1은 오른쪽으로, 2는 위쪽으로, 3은 왼쪽으로, 4는 아래쪽으로 한 칸씩 그리는 것을 말한다.
예를 들어 아래 그림의 다각형 (2)는 점 A에서 시작하여 화살표 방향으로 모양수열 1411433322를 따라서 그린 것이다. 다각형 (3)은 점 B에서 시작하여 화살표 방향으로 모양수열 3221411433을 따라서 그린 것이다. 또한 다각형(4)는 점 C에서 시작하여 화살표 방향으로 모양수열 4411123323을 따라서 그린 것이다. 다각형 (2), (3), (4)는 다각형 (1)과 같으므로 모양수열들 1411433322, 3221411433, 4411123323은 모두 같은 다각형을 그릴 수 있다. 단, 다각형이 회전된 것이나 뒤집어진 것은 같은 다각형이 아니다. 그러므로 아래 그림의 다각형 (5)와 (6)은 다각형 (1)과 다르다.
한 개의 표본 모양수열과 여러 모양수열들이 주어졌을 때 표본 모양수열과 같은 다각형을 그릴 수 있는 모양수열들을 모두 찾는 프로그램을 작성하시오.
첫째 줄에는 표본 모양수열의 길이(숫자의 개수)가 주어지고, 둘째 줄에는 표본 모양수열이 주어진다. 셋째 줄에는 모양수열의 개수가 주어지고 넷째 줄부터는 각 줄에 표본 모양수열과 같은 길이의 모양수열이 하나씩 주어진다. 단, 모양수열들의 개수는 최대 100 개이고 모양수열의 길이는 최대 50 이다. 모양수열의 각 숫자 사이에는 빈칸이 하나 있다.
출력
첫째 줄에는 입력된 표본 모양수열과 같은 다각형을 그리는 모양수열들의 개수를 출력한다. 둘째 줄부터는 각 줄에 표본 모양수열과 같은 다각형을 그릴 수 있는 모양수열을 출력한다. 출력되는 모양수열의 숫자들은 한 칸 띄고 출력한다.
처음에는 좌표계를 기준으로 문제를 풀려다, 좌표가 아닌 '방향'으로 생각하면 더 문제가 쉽다는 걸 깨달았다.
방향을 기준으로 생각한다면, 모양수열의 어느 부분에서 시작하던 간에 결국 같은 모양이 나온다. 즉 모양수열을 rotate하였을 때 두 모양수열이 같다면 같은 모양수열이다.
또한, 반대로 그리는 경우도 생각해 볼 수 있다. 반대 방향으로 그린다는 말의 의미는 모양수열의 '화살표 방향이 반대'이며 '진행 방향이 반대'가 된다. 즉 이렇게 반대로 생성된 모양수열을 rotate하였을 때 두 모양수열이 같다면 같은 모양수열이다.
rotate를 지원하는 deque 자료구조를 사용하면 편하다. 또한 표본 모양수열과 이를 뒤집은 모양수열을 미리 생성하는 게 더 편하다.
풀이 코드
from collections import deque
import sys
input = sys.stdin.readline
convert = lambda x : (x + 2) % 4 if x != 2 else 4
N = int(input())
standard = deque(map(int, input().split()))
rev_standard = deque(map(convert, standard))
rev_standard.reverse()
cnt = 0
result = list()
for _ in range(int(input())) :
ctr_grp = deque(map(int, input().split()))
tmp = ctr_grp.copy()
for _ in range(N) :
if standard == tmp or rev_standard == tmp :
cnt += 1
result.append(ctr_grp)
tmp.rotate(1)
print(cnt)
for _lst in result :
print(*_lst)
