요즘 신나게 구현 문제를 풀다보니, 구현에 대한 테크닉들이 몇개씩 나오고 있어서, 하나씩 기록해보려고 한다. 감시 문제에서는 dx,dy의 좌표를 방향으로 생각하고 n진법으로 나타내는 테크닉이 있었는데, 이번에는 생각보다 꽤 자주나오는 NxN 배열 90도 돌리기이다.
배열 회전하기
사실 , NxM 배열을 90도 회전하는 방법은 아주 많다. 하지만, 원리를 이해하고 구현할 방법을 정해놓지 않으면 자칫 헷갈리기 쉬운 문제 중 하나인 것 같다. 우선, 배열을 90도 회전한다는 의미부터 짚고 가보자. 4x4 행렬을 오른쪽으로 90도 회전하면 아래와 같이 움직인다.
이때, 왼쪽 배열을 A, 오른쪽 배열을 B라고 했을 때, 좌표 관계를 알아보자.
초록색 형관팬부분의 열이 B의 첫번째 행이 되었다.- 쭉 나열해보자면,
(0,0) -> (0,3),(1,0) -> ( 0,2),(2,0) -> (0,1),(3,0)->(0,0)이 되었다. 관계를 찾아보자면, A의 Column은 B의 Row가 되었고, A의 Row가 증가할수록, B의 Column은 감소하는 것으로 파악이 된다. A의 Row와 B의 colmun의 합이 일정하다라고도 표현할 수 있다.
A Row + B column = N-1 (좌표) 이기 때문에, A[Row] = N-1 - B colmun이다.
정리해보자면, 우리는 결국 B를 알아내고 싶은것이기 때문에, B를 기준으로 식을 작성하면 된다.
약간 외우듯이, 작성을 해놓으면 헷갈리지 않고 쭉 작성할 수 있을 것 같다.
B[Row][Colmun] = A[N-1-Colmun][Row] 이다.
//90도 회전
for(int i=0;i<N;i++){
for(int j=0;j<N;j++){
board_B[i][j] = board_A[N-1-j][i];
}
}
90도,180도, 270도는 어떻게 회전하나요 ?
이걸 1번 해주면 90도, 2번 해주면 180도,3번해주면 270도이다.
즉, 이 연산을 반복해서 해주면된다.
가로,세로가 다르다면, 어떻게 해줄 수 있을까?
예를들어서, 2x5 같은 배열을 90도 회전한다고 생각해보자. 5x2배열이 된다!!
차이점은 간단하다. 가로 세로가 바뀌는 점만 주의 해주면된다. 아래는 의사코드로 작성하려고 한다.
int N = 2;
int M = 5;
int board_A[100][100];
int board_B[100][100];
for(int i=0;i<M;i++){
for(int j=0;j<N;j++){
board_B[i][j] = board_A[M-1-j][i];
}
}
swap(N,M);
