2 차원 배열을 90도 회전

Question

배열 조작 연습 중 소품이 2 차원 배열을 90도 회전시키는 것이 자주 발생합니다. 다양한 프로그래밍 언어로이를 수행하는 방법에 대한 답변이있는 몇 가지 게시물이 있습니다. 내 질문은 거기에있는 답변 중 하나를 명확히하고 유기적 인 방식으로 대답을 얻기 위해 어떤 종류의 사고 과정이 필요한지 탐구하는 것입니다.

다음과 같이 내가 찾은이 문제에 대한 해결책은 간다 :

public static void rotate(int[][] matrix,int n) 
{ 
    for(layer = 0;layer < n/2;++layer){ 
     int first = layer; 
     int last = n -1 - layer; 
     for(int i = first;i<last;++i){ 
     int offset = i - first; 
     int top = matrix[first][i]; 
     matrix[first][i] = matrix[last-offset][first]; 
     matrix[last-offset][first] = matrix[last][last-offset]; 
     matrix[last][last-offset] = matrix[i][last]; 
     matrix[i][last] = top; 
     } 
    } 
} 

나는 약간 위의 코드가 시도 무슨 생각으로 가지고, 그것은 네 가지를 수행하여 사지/코너를 교환한다 일부 셀 오프셋으로 구분 된 다른 셀에 대해 동일한 작업을 수행합니다.

이 코드를 실행하면 작동한다는 것을 알 수 있습니다. 위의 주어진 알고리즘에 대한 수학적 근거는 얻을 수 없습니다. '층', '처음', '마지막'및 오프셋의 이유는 무엇입니까?

어떻게 '마지막'이 n-1-layer이 되었습니까? 오프셋은 왜 i-first입니까? 처음에는 오프셋이 무엇입니까?

누군가가이 알고리즘의 기원을 설명하고 해결책을 생각해 내기 위해 생각 프로세스를 단계적으로 수행 할 수 있다면 큰 도움이 될 것입니다.

감사

Answer 1

아이디어는 작은 작업에 큰 작업 (정방 행렬을 회전)을 파괴하는 것입니다.

먼저 정사각형 행렬을 동심 사각 링으로 분해 할 수 있습니다. 링의 회전은 다른 링의 회전과는 독립적이므로 행렬을 회전 시키면 각 링이 하나씩 회전합니다. 이 경우에는 가장 바깥 쪽 반지에서 시작하여 안쪽으로 작업합니다. 우리는 layer (또는 first, 똑같은 것)을 사용하여 반지를 센다. 그리고 중간에 도착하면 멈추어진다. 그래서 그것이 n/2까지 올라간다. (이것이 홀수이고 심지어 n에 대해 작동하는지 확인하는 것이 가치가 있습니다.) last = n - 1 - layer을 사용하여 링의 "먼 쪽"을 추적하는 것이 유용합니다. 예를 들어 5x5 매트릭스에서 첫 번째 링은 first=0에서 시작하여 last=4에서 끝나고 두 번째 링은 first=1에서 시작하여 last=3에서 끝나는 식으로 계속됩니다.

반지를 회전하는 방법은 무엇입니까? 위쪽 가장자리를 따라 오른쪽 가장자리를 따라 왼쪽 가장자리를 따라 위쪽 가장자리를 따라 왼쪽으로 이동합니다. 각 단계에서 네 개의 값을 서로 바꿉니다. 변경되는 좌표는 i이고 단계 수는 offset입니다. 예를 들어 두 번째 링을 걷는 경우 i은 {1,2,3}이되고 offset은 {0,1,2}가됩니다.