[BOJ] 백준 2641 다각형 그리기

출처: https://www.acmicpc.net/problem/2641

 Input 

10

1 4 1 1 4 3 3 3 2 2

3

3 2 2 1 4 1 1 4 3 3

1 4 4 3 3 3 2 1 1 2

4 4 1 1 1 2 3 3 2 3

 

 Output 

2

3 2 2 1 4 1 1 4 3 3

4 4 1 1 1 2 3 3 2 3

문제에서 모양수열은 한 개의 다각형을 그리기에 출발점만 다를 뿐 그려지는 모양은 같습니다.

- 점 A에서 출발하는 다각형 (2): 1 4 1 1 4 3 3 3 2 2

- 점 B에서 출발하는 다각형 (3): 3 2 2 1 4 1 1 4 3 3  

그렇기에 이차원 배열에 따로 다각형 모양을 그려서 비교하지 않고, 

주어지는 모양수열 원소를 하나의 출발점으로 생각하며 똑같은 경로를 그리는지 확인합니다.

 

(3) 다각형이 (2) 다각형과 같은지 확인하기 위해서 아래 3개 지점에서 시작하여 서로 비교합니다.

3 2 2 1 4 1 1 4 3 3 ← 다각형 (2)의 첫번째 원소가 같은 지점만 확인.

결과적으로 [1 4 1 1 4 3 3 3 2 2]와 같은 구간이 존재하기에 다각형 모양이 같은 모양수열이라고 볼 수 있습니다.

 

또한, 다각형을 그려나갈때 반대 방향으로 모양이 같을 수 있으므로

입력받은 모양수열을 오른쪽(1) ↔ 왼쪽(3) | 아래쪽(4) ↔ 위쪽(2)로 바꿔서도 비교합니다.

ex) 다각형 (3) = [3 2 2 1 4 1 1 4 3 3] ↔ [1 4 4 3 2 3 3 2 1 1]

 

---

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
int N, M, answer;
int check[50], leftPivot[50], rightPivot[50], arr[50][50];
void printArr(int idx) {
    for (int i = 0; i < N; ++i) {
        printf("%d ", arr[idx][i]);
    }
    printf("\n");
}
int leftRotation(int idx, int k, int *pivot) {
    
    int cnt = N, pIdx = 0;
    while (cnt--) {
        // 일치하지 않는 경우
        if (pivot[pIdx] != arr[idx][k]) {
            // printf("불일치!!\n");
            return 0;
        }
        // k는 순환되도록
        pIdx++, k--;
        if (k < 0) k = N - 1;
    }
    return 1;
}
int rightRotation(int idx, int k, int *pivot) {
    int cnt = N, pIdx = 0;
    while (cnt--) {       
        // 일치하지 않는 경우
        if (pivot[pIdx] != arr[idx][k]) {
            // printf("불일치!!\n");
            return 0;
        }
        // k는 순환되도록
        pIdx++, k++;
        if (k >= N) k = 0;
    }
    return 1;
}

int main() {
    // freopen("input.txt", "r", stdin);
    int i, j, k;
    scanf("%d", &N);
    // 정방향
    for (i = 0; i < N; ++i) {
        scanf("%d", leftPivot + i);
    }
     
    // 반대방향
    for (i = 0; i < N; ++i) {
        switch (leftPivot[i]){
        case 1: rightPivot[i] = 3;
            break;
        case 2: rightPivot[i] = 4;
            break;
        case 3: rightPivot[i] = 1;
            break;
        case 4: rightPivot[i] = 2;
            break;
        }
    }

    scanf("%d", &M);
    for (i = 0; i < M; ++i) {
        for (j = 0; j < N; ++j) {
            scanf("%d", &arr[i][j]);
        }

        // 왼쪽으로 탐색하는 경우
        for (k = 0; k < N; ++k) {
            if (leftPivot[0] == arr[i][k] && leftRotation(i, k, leftPivot)) {
                answer++;
                check[i] = 1;
                break;
            }
        }
        // leftRotation()으로 끝나지 않은 경우 오른쪽으로 탐색
        if (!check[i]) {
            for (k = 0; k < N; ++k) {
                if (leftPivot[0] == arr[i][k] && rightRotation(i, k, leftPivot)) {
                    answer++;
                    check[i] = 1;
                    break;
                }
            }
        }

        if (!check[i]) {
            for (k = 0; k < N; ++k) {
                if (rightPivot[0] == arr[i][k] && leftRotation(i, k, rightPivot)) {
                    answer++;
                    check[i] = 1;
                    break;
                }
            }
        }
        if (!check[i]) {
            for (k = 0; k < N; ++k) {
                if (rightPivot[0] == arr[i][k] && rightRotation(i, k, rightPivot)) {
                    answer++;
                    check[i] = 1;
                    break;
                }
            }
        }
    }
    
    printf("%d\n", answer);
    for (i = 0; i < M; ++i) {
        if (check[i]) printArr(i);
    }
}