> 두 정삼각형 > Silver I > #[[구현]] ### 문제 요약 i번째 줄에 i개의 수(0 또는 1)를 배치한 정삼각형 A, B가 주어집니다. i의 최댓값은 N으로 주어집니다. N은 10 이하입니다. A를 원하는 만큼 회전 및 대칭시킬 수 있을 때, B와 동일한 위치에 있는 수의 값이 다른 위치의 개수의 최솟값을 계산해야 합니다. ### 해설 해설에 들어가기 전에 2차원 배열에 대해 명확히 해야 할 것이 있습니다. 이 문제를 포함해 일반적으로 2차원 배열을 입력받을 때 다음과 같이 구현합니다. ```cpp for (int i = 0; i < N; ++i) { for (int j = 0; j <= i; ++j) { cin >> A[i][j]; } } ``` 그런데 입력은 다음과 같이 들어옵니다. ``` A[0][0] A[1][0] A[1][1] A[2][0] A[2][1] A[2][2] ``` 따라서 `A[i][j]`에서 '아래쪽으로 한 칸' 이동하면 `A[i + 1][j]`이고, '오른쪽으로 한 칸' 이동하면 `A[i][j + 1]`입니다. 초보자 입장에서 헷갈리기 쉬운데, 꼭 기억해 주세요. 이제 문제를 해설하겠습니다. 우선 정삼각형을 회전 및 대칭시켰을 때 가능한 수 배치의 가짓수는 6입니다. 회전은 3가지, 대칭은 2가지만 가능하기 때문입니다. 따라서 모든 수 배치를 구현하면 되는데, 6가지를 각각 구하도록 구현하기에는 작성해야 할 코드가 너무 많아지기 때문에 회전과 대칭을 각각 구현해서 반복 수행하는 것이 정신 건강에 이롭습니다. 대칭은 구현이 비교적 쉬운데, 수직선 기준으로 대칭 변환할 때 모든 수의 수직선 기준 높이는 그대로이므로 `A[i][j]`가 `A[i][i - j]`로 이동함을 알 수 있습니다. 회전은 일반적인 2차원 배열을 다룰 때 구현하게 되는 90도 회전이 아닌 120도 회전을 구현해야 하는데, 저는 이것을 두 가지 변환의 합성으로 생각했습니다. ``` A[0][0] A[1][0] A[1][1] A[2][0] A[2][1] A[2][2] ``` 위 정삼각형 배열을 우선 90도 회전합니다. 시계 방향 90도 회전은 보통 `A[i][j]`가 `A[j][N - 1 - i]`로 이동하는 것을 이용하여 구현합니다. (이것이 잘 와닿지 않는다면, `A[i][j]`를 `A[j][i]`로 바꿔 대각선 기준으로 대칭 변환(사실은 transpose)한 다음 `A[j][N - 1 - i]`로 수직선 기준으로 대칭 변환하는 것으로 쪼개서 생각해도 좋습니다.) ``` A[2][0] A[1][0] A[0][0] A[2][1] A[1][1] A[2][2] ``` 실제로 위와 같이 됩니다. 90도가 돌아갔는데, 비교해야 할 정삼각형 배열 B와 모양이 다르므로 위치를 내릴 수 있는 수들은 최대한 밑으로 내려 모양을 맞춰야겠습니다. 그런데 앞선 그림을 보면 인덱스가 좀 어지러워서 또다른 변환을 적용한 뒤의 인덱스를 일반화하기 어려워 보입니다. 그러니 인덱스가 어지럽지 않은 새로운 그림을 그려서 일반화를 시도한 뒤, 두 변환의 결과를 '합성'하는 방식을 사용해 봅시다. (기초 선형대수학에서 말하기를, 선형변환끼리 합성한 것은 여전히 선형변환입니다. 다행히 '90도 회전'과 '밀어서 모양 맞추기'는 둘 다 선형변환에 해당해, 두 가지를 따로 생각한 뒤 합성해도 됩니다. 위에서 90도 회전이 사실은 둘로 쪼개질 수 있다고 언급할 때 나온 대칭 변환들도 모두 선형변환입니다.) ``` A[0][0] A[0][1] A[0][2] A[1][0] A[1][1] A[2][0] ``` ``` A[0][0] A[1][0] A[0][1] A[2][0] A[1][1] A[0][2] ``` 위 그림에서 아래 그림으로 위치를 바꾸는 겁니다. 이제 `A[i][j]`가 `A[i + j][j]`로 이동했다는 것이 잘 보이네요. 이제 두 변환이 명확해졌습니다. 1. `A[i][j]`가 `A[j][N - 1 - i]`로 이동 2. `A[i][j]`가 `A[i + j][j]`로 이동 2번째 변환이 `A[p][q]`를 `A[p + q][q]`로 이동시키는 것이므로, `p = j, q = N - 1 - i`로 두면 합성한 최종 결과물은 `A[j + N - 1 - i][N - 1 - i]`가 됩니다. 회전에 대한 설명이 길었는데, 문제를 풀기 위한 구현은 다음과 같이 하면 되겠습니다: ``` for 대칭 2가지 경우 for 회전 3가지 경우 배열 C에 A를 복사 for i, j A[j + N - 1 - i][N - 1 - i] = C[i][j] A, B의 다른 값의 개수 계산해서 정답 업데이트 배열 D에 A를 복사 for i, j A[i][i - j] = D[i][j] ``` ### 배울 점 이 문제를 풀면서 2차원 배열의 대칭과 회전을 깊이 이해할 수 있습니다. 이는 (주로 코딩 테스트에서) 많은 구현 및 시뮬레이션 문제를 빠르고 정확하게 해결하는 능력의 밑바탕이 됩니다.