재밌는 KMP 놀이 시작

BOJ 2641 - 다각형그리기 링크
(2022.10.20 기준 S2)
(이거 치팅하면 무조건 걸릴걸?)

문제

모양수열로 표시되는 모눈종이에 다각형을 그리는 방법이 있다. 모양수열은 1~4 사이의 숫자가 연속되어 나열되어 있고, 1은 오른쪽, 2는 위쪽, 3은 왼쪽, 4는 아래쪽으로 한 칸씩 그리는 것이다.
한 개의 표본 모양수열과 여러 모양수열들이 주어졌을 때, 표본 모양수열과 같은 다각형이 그려지는 모양수열들을 모두 찾기. 단, 회전된 것이나 뒤집어진 것은 같은 다각형이 아니다.

알고리즘

표본 모양수열과 여러 모양수열들을 비교하는 문제. 그려지는 방법을 잘 생각하여 비교하는 방법을 구현해야 한다.

풀이

문제 예제의 표본 모양수열을 직접 그려보면
이렇게 그려진다.

모양수열의 첫번째를 직접 그려보면
빨간색 방향대로 그려지게 된다.
다각형이 그려지는 방법은 회전하는 것이므로 중간에서 시작해도 다시 돌아와서 그대로 똑같이 진행되면 똑같은 다각형이 되는 것이다.
이는 다음과 같다.
비교하고자 하는 두 모양수열 중 하나를 두배로 늘려서, 나머지 모양수열이 포함되는지 확인하면 된다.

다음은 모양수열의 세번째를 직접 그려보자.
표본 모양수열의 반대 방향으로 그려진 것이 보인다.
이는 다음과 같다.
비교하고자 하는 두 모양수열 중 하나를 반대로 하여 비교를 하는 것이다.

반대로 하는 방법은 수열을 뒤집어서 1 -> 3, 2 -> 4, 3 -> 1, 4 -> 2로 바꾸면 된다.

list(map(lambda x: (x + 1) % 4 + 1, 표본모양수열[::-1]))

이 문제의 핵심은 이게 끝이다.
난이도가 실버인 만큼 in 연산자를 써서 포함되는지 확인하면 되겠지만
나는 KMP를 사용하였다. 이제부턴 KMP를 어떻게 쓸지 설명하겠다.

표본 모양수열은 1개이고, 비교할 모양수열은 여러 개이다. 포함되는지 확인할 대상은 파이 함수를 만들어야 하므로, 표본 모양수열의 파이 함수를 만들고, 모양수열을 두배로 늘려 표본 모양수열이 포함되는지 확인하자. 그리고 반대 방향으로의 모양수열을 만들어야 하는데, 표본 모양수열의 반대방향을 반대방향의 파이 함수와 함께 만들어 놓자. 그리고 비교를 하는 것이다.

이런 식으로 비교를 해나가는 것이다.

그냥 웬만하면 in 연산자 쓰자. 심심해서 KMP 써봄..

코드

# KMP
import sys; input = sys.stdin.readline

# T : 표본 모양수열
# 각 모양수열 두 개를 붙여서 표본 모양수열이 포함되어 있는지를 KMP로 비교
# 그리는 방향이 반대로가 될 수 있으므로
# 1 -> 3, 2 -> 4, 3 -> 1, 4 -> 2 로 바꿔서도 KMP를 돌려야 한다.
# lambda x: (x + 1) % 4 + 1 을 적용하고 뒤집어주면 된다.
t = int(input())
T = list(map(int, input().split()))
reverse_T = list(map(lambda x: (x + 1) % 4 + 1, T[::-1])) # 반대 방향

# 표본 모양수열 pi 함수
pi = [0] * t
i = 0
for j in range(1, t):
    while i and T[i] != T[j]:
        i = pi[i - 1]
    if T[i] == T[j]:
        i += 1
        pi[j] = i

# 반대 방향 표본 모양수열 pi 함수
reverse_pi = [0] * t
i = 0
for j in range(1, t):
    while i and reverse_T[i] != reverse_T[j]:
        i = reverse_pi[i - 1]
    if reverse_T[i] == reverse_T[j]:
        i += 1
        reverse_pi[j] = i

result = []
for _ in range(int(input())):
    p = t * 2 # 모양수열의 길이는 t의 2배
    original_P = list(map(int, input().split())) # 모양수열
    P = original_P * 2 # 두 개를 붙인다.
    i = 0
    for j in range(p):
        while i and T[i] != P[j]:
            i = pi[i - 1]
        if T[i] == P[j]:
            if i == t - 1: # 표본 모양수열의 끝까지 찾았다면
                result.append(original_P) # 결과에 저장 후 KMP 중단
                break
            i += 1
    else: # 표본 모양수열이 찾아지지 않았다면 반대 방향 표본 모양수열을 찾아보자.
        i = 0
        for j in range(p):
            while i and reverse_T[i] != P[j]:
                i = reverse_pi[i - 1]
            if reverse_T[i] == P[j]:
                if i == t - 1: # 표본 모양수열의 끝까지 찾았다면
                    result.append(original_P) # 결과에 저장 후 KMP 중단
                    break
                i += 1

print(len(result))
for res in result:
    print(*res)

여담

KMP 문제는 재밌는데 많지가 않다. 많이 풀고 싶은데... 속상해.