[백준 28217] 2023 정올 1차 두 정삼각형

문제 출처 : https://www.acmicpc.net/problem/28217

28217번: 두 정삼각형

이 문제는 2023년 정보 올림피아드 중등부 1차 1번 문제로 출제된 두 정삼각형이라는 문제 입니다.

정 삼각형을 회전시키거나, 대칭으로 만들어 값을 비교하는 문제 입니다. N의 크기도 크지 않아 특별한 알고리즘을 사용하지 않아도 문제가 해결될 것 같습니다. 다만 회전시키거나 대칭을 만드는 것이 쉽지 않아 보입니다. 이런 문제를 해결하기 위해 배열을 회전 시키는 방법에 대해 알아보았지만 사각형을 회전 시키는 것과 삼각형을 회전시키는 것이 쉽지는 않아 보입니다.

먼저 아래의 2차원 배열 회전시키는 방법을 충분히 익히고 다음 내용을 확인해보시기 바랍니다.

https://davincicoding.tistory.com/83

2차원 배열 회전하기

삼각형 회전 이해하기

삼각형을 회전 시키는 방법은 다음과 같은 과정을 거치게 됩니다.

1. 2차원 배열을 시계방향으로 90도 회전
2. 배열을 바닥으로 이동

이렇게 두 단계를 거쳐야 삼각형이 문제에서 원하는 120도 회전을 하는 것과 같은 효과를 얻습니다.

90도 회전을 하는 것은 위에서 배운 2차원 배열을 회전하는 것과 똑같습니다. 다음으로 밑으로 보내는 것은 기본 행의 값 i에다가 j의 행의 크기만큼 빼주면 됩니다. 행이 0, 1, 2로 커지기 때문에 첫 번째 열에는 0을 빼주고, 첫 번째 열은 1을 빼주고, 2번째 열은 2를 빼주면 원하는 형태가 됩니다. 코드로 알아보면 다음과 같습니다.

for i in range(N):
    for j in range(i + 1):
        b[i][j] = a[N - 1 - j][i]

이 코드가 90도 만큼 시계방향으로 돌린 코드 입니다. 여기에 행을 j 값으로 빼주는 것입니다.

for i in range(N):
    for j in range(i + 1):
        b[i][j] = a[N - 1 - j][i - j]

이렇게 행의 값에다가 j값을 빼주게 되면 원하는 삼각형의 회전이 완성 됩니다. 그럼 가장 어려운 부분을 해결하였으니 코드를 직접 작성해 보겠습니다.

코드 작성

입력 받기

mii = lambda : list(map(int, input().split()))
N = int(input())
A = []
for _ in range(N):
    tmp = mii()
    A.append(tmp)

B = []
for _ in range(N):
    tmp = mii()
    B.append(tmp) 

배열의 크기 N과 두 삼각형 A, B를 입력 받았습니다. 다음으로 삼각형을 회전하고, 대칭 이동 시키고, 두 삼각형의 값을 비교하는 코드를 작성해 보겠습니다.

삼각형 회전

def rotate(A):
    tmp = [[0] * N for _ in range(N)]
    
    for i in range(N):
        for j in range(i + 1):             
            tmp[i][j] = A[N - 1 - j][i - j]
    
    return tmp

삼각형을 회전 시키는 코드 입니다. 위에서 말했듯이 90도 회전을 시킨다음 밑으로 내려주면 삼각형의 120도 회전과 같게 됩니다.

대칭 이동시키기

def symmetry(A):
    tmp = [[0] * N for _ in range(N)]

    for i in range(N):
        for j in range(i + 1):
            tmp[i][j] = A[i][i - j]
    return tmp

대칭 이동은 중심을 기준으로 뒤집는 것과 같습니다. 따라서 i값은 그대로 놔두고 j값만 i - j로 변경하였습니다. 대칭은 결국 이동한 만큼 끝값에서 빼준것과 같습니다.

왼쪽부터 a만큼 떨어져 있다면 대칭인 값은 오른쪽 끝인 N에서부터 a만큼 떨어진 값이 됩니다. 따라서 대칭값은 N - a라 할 수 있습니다. 하지만 삼각형에서 끝값은 고정된 N값이 아니라 크기만큼 변합니다. 따라서 N에서 빼주는 것이 아니라 i값에서 빼주게 됩니다. 그렇기에 i - j 값이 된 것입니다.

비교하기

def calculate(A, B):
    cnt = 0
    for i in range(N):
        for j in range(i + 1):
            if A[i][j] != B[i][j]:
                cnt += 1
    return cnt

A와 B를 비교하는 코드 입니다. A, B 삼각형을 돌면서 두 값이 차이가 날 때마다 cnt 값을 늘려줍니다.

계산하기

그럼 최소값이 몇인지 계산하는 코드를 작성해 보겠습니다.

ans = 1e9

for i in range(3):
    ans = min(ans, calculate(A, B))
    A = rotate(A)

A = symmetry(A)
for i in range(3):
    ans = min(ans, calculate(A, B))
    A = rotate(A)

print(ans)

삼각형 A를 회전시켜가며 B와 비교를 합니다. 120도시 3번 돌려주면 모든 회전에 대해 비교가 완료 됩니다. 그리고 대칭이동 시켜주어 또 3회전해가며 비교를 해줍니다. 이렇게 총 6번 비교하여 최종적으로 제일 작은 값을 출력하면 됩니다.

전체 코드

전체 코드를 확인해 보겠습니다.

mii = lambda : list(map(int, input().split()))
N = int(input())
A = []
for _ in range(N):
    tmp = mii()
    A.append(tmp)

B = []
for _ in range(N):
    tmp = mii()
    B.append(tmp)

def rotate(A):
    tmp = [[0] * N for _ in range(N)]
    
    for i in range(N):
        for j in range(i + 1):             
            tmp[i][j] = A[N - 1 - j][i - j]
    
    return tmp

def symmetry(A):
    tmp = [[0] * N for _ in range(N)]

    for i in range(N):
        for j in range(i + 1):
            tmp[i][j] = A[i][i - j]
    return tmp

def calculate(A, B):
    cnt = 0
    for i in range(N):
        for j in range(i + 1):
            if A[i][j] != B[i][j]:
                cnt += 1
    return cnt

ans = 1e9

for i in range(3):
    ans = min(ans, calculate(A, B))
    A = rotate(A)

A = symmetry(A)
for i in range(3):
    ans = min(ans, calculate(A, B))
    A = rotate(A)

print(ans)