알고리즘 설계 실습 - 두 정삼각형

---

문제

첫 번째 줄에는 1개의 수를, 두 번째 줄에는 2개의 수를, …, N번째 줄에는 N개의 수를 아래 그림 과 같이 배치한 같은 크기의 정삼각형 A, B가 주어진다. 각 위치에 있는 수는 0 또는 1이다.

정삼각형을 시계방향 또는 반시계 방향으로 120도 회전시키거나 좌우로 대칭시킬 수 있다. 예를 들어, 위 그림의 정삼각형 A를 회전시켜서 얻을 수 있는 정삼각형들은 다음과 같다.

A를 횟수 제한 없이 회전시키거나 대칭시켜 B와 차이가 최소로 나게 하라. 이때 차이가 얼마인지 구하라.

차이라는 것은 일치하지 않는 부분의 개수이다.

 

입력

첫 번째 줄에 A, B의 크기 N이 주어집니다. 두 번째 줄부터 N+1번째 줄까지, 정삼각형 A의 각 위치에 있는 수들이 주어집니다. i+1 (1≤i≤N)번째 줄에는 정삼각형 A의 i번째 줄에 있는 i개의 정수가 왼쪽부터 공백을 사이에 두 고 순서대로 주어집니다. N+2번째 줄부터 2N+1번째 줄까지, 정삼각형 B의 각 위치에 있는 수들이 주어집니다. i+N+1 (1≤i≤N)번째 줄에는 정삼각형 B의 i번째 줄에 있는 i개의 정수가 왼쪽부터 공백을 사이에 두고 순서대로 주어집니다.

 

출력

첫 번째 줄에 A를 원하는 만큼 회전, 대칭시켜서 얻을 수 있는 B와의 차이의 최솟값을 출력하세 요.

 

제한사항

1. 주어지는 모든 수는 정수입니다.

2. 1≤N≤10

3. 정삼각형 A, B의 각 위치에 있는 수는 0 또는 1입니다.

 

EX)

입력 예시

4

0

1 1

1 0 0

1 0 0 0

0

0 0

0 0 1

1 1 1 0

 

출력 예시

0

---

소스코드

import sys

input = sys.stdin.readline

n = int(input())

triangle_a = []
triangle_b = []
for _ in range(n):
    triangle_a.append(list(map(int, input().split())))
for _ in range(n):
    triangle_b.append(list(map(int, input().split())))

#반시계방향 회전함수
#index값을 이용하여 rotate 구현
def rotate(triangle):
    tmp = []
    for i in range(1,n+1):
        tmp.append([i for i in range(i)])

    for i in range(n):
        for j in range(i,n):
            tmp[n-i-1][j-i] = triangle[j][i]

    return tmp

#차이를 계산하는 함수
def calculate(triangle_a,triangle_b):
    cnt = 0

    for i in range(n):
        for j in range(i,n):
            if triangle_a[j][i] != triangle_b[j][i] :
                cnt+=1

    return cnt

#최소값이 될 수 없는 수를 설정하여 min()계산후에 적절한 값이 나오도록 함
result = 10000000

#회전해가며 차이를 계산하며 차이의 최값 갱신
for i in range(3):
    result = min(result,calculate(triangle_a,triangle_b))
    triangle_a = rotate(triangle_a)

#좌우로 뒤집는 과정
flip = []
for i in range(1,n+1):
        flip.append([i for i in range(i)])


for i in range(n):
    for j in range(i+1):
        flip[i][i-j] = triangle_a[i][j]

#뒤집기를 적용해서 다시 rotate 3번 조사
for i in range(3):
    result = min(result,calculate(flip,triangle_b))
    flip = rotate(flip)

print(result)

rotate함수를 index를 바꾸는 방식으로 구현한다. 또한 calcutate함수는 A삼각형과 B삼각형에서 같은 index를 비교하여 다르면 1씩 counting하는 방식을 이용한 함수이다. rotate를 3번 반복하며 min값을 계속 갱신해주고 flip한 뒤에 rotate를 3번 반복하여 min값을 다시 갱신한다.

---