[BOJ] 2641 다각형그리기(python)

문제

모눈종이에 다각형을 그리려고 한다. 그리는 방법은 모양수열로 표시된다. 모양수열은 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 이다. 모양수열의 각 숫자 사이에는 빈칸이 하나 있다.

출력

첫째 줄에는 입력된 표본 모양수열과 같은 다각형을 그리는 모양수열들의 개수를 출력한다. 둘째 줄부터는 각 줄에 표본 모양수열과 같은 다각형을 그릴 수 있는 모양수열을 출력한다. 출력되는 모양수열의 숫자들은 한 칸 띄고 출력한다.

풀이

다각형의 모양을 어떻게 정의하느냐가 제일 고민이였다.
천천히 예시로 제공된 값들을 보며 찾은 결과, 십자카드 문제에서 시계수를 구할 때와 같은 방식으로 풀면 된다고 생각했다.
arr[i:] + arr[:i]가 표본 모양수열과 같다면 그 모양수열은 같은 다각형이 되기에 이를 이용해서 풀려고 했다.
다각형을 그릴 때 반대방향으로 그릴 경우에는 1과 3을 서로 바꾸고 2와 4를 서로 바꾼 다음 역순을 사용하면 된다는 결론까지 얻었는데, 한참을 어떻게 바꾸지 하는 고민을 했다.
생각보다 답은 너무 허무하게 나왔는데, 그냥 dict로 만들어서 매핑하면 되더라...

import sys

num_moves = int(sys.stdin.readline())  # 표본 모양수열 길이
sample_form = list(map(int, sys.stdin.readline().split()))  # 표본 모양수열
num_shapes = int(sys.stdin.readline())  # 모양수열 갯수
shapes = []  # 모양수열 담을 리스트
for _ in range(num_shapes):
    shapes.append(list(map(int, sys.stdin.readline().split())))

# 1,3 / 2,4 매핑할 dict
reverse = {1:3, 2:4, 3:1, 4:2}
sames = []
for shape in shapes:
    reverse_shape = list(map(lambda x: reverse[x], shape))[::-1]  # 1,3 / 2,4 매핑 후 순서 뒤집기
    
    if shape == sample_form or reverse_shape == sample_form:
        sames.append(shape)
        continue
    
    # 십자카드 문제와 같은 풀이방법
    for i in range(1, num_moves):
        tmp = shape[i:] + shape[:i]
        reverse_tmp = reverse_shape[i:] + reverse_shape[:i]
        if tmp == sample_form or reverse_tmp == sample_form:
            sames.append(shape)
            break

print(len(sames))
for s in sames:
    print(' '.join(list(map(str, s))))