문제 이해 단계
https://www.acmicpc.net/problem/20327
20327번: 배열 돌리기 6
크기가 2N×2N인 배열이 있을 때, 배열에 연산을 R번 적용하려고 한다. 연산은 8가지가 있고, 연산에는 단계 ℓ (0 ≤ ℓ < N)이 있다. 단계 ℓ은 배열을 부분 배열로 나눌때 사용하는 값이며, 부분
www.acmicpc.net
이번 문제는 너무 길기 때문에 백준 링크로 대체한다
요약하자면, 구현해야 하는 것이 총 8가지인데,
구현해야 할 기능은 총 4가지이다.
이 문제에서 특이한 점은 단계 L이란 것이 존재하는데,
L은 부분배열을 의미한다.
부분 배열은 2^L*^L 크기여야 한다.
구현해야 하는 K는
1,2번 -> 같은 부분 배열에서 상하/좌우 배열 반전
3,4번 -> 같은 부분 배열에서 시계/반시계 방향으로 배열 90도 돌리기
5,6번 -> 다른 3개의 부분 배열과 상하/좌우 배열 반전
7,8번 -> 다른 3개의 부분 배열과 90도 돌리기
이걸 구현하는 게 이번 문제이다.
문제 접근 단계
배열 돌리기 시리즈 문제인데,
딱 봐도 유형은 구현 문제라고 줬다. 근데 구현할 게 너무 많다..
부분 배열 L 구현
가장 첫 번째로 문제가 되는 부분이다.
부분 배열 L을 어떻게 구현할 것인가.
2^N*2^N배열을 만들었고
이걸 가로와 세로가 L인 정사각형으로 나눠 인식해야 한다.
가장 간단한 방법은
이 부분 배열들을 그냥 하나의 배열로 보는 것이다.
그럼 한 칸씩 움직이는 게
부분 배열 L로 이루어진 칸으로 움직이는 것이 된다.
즉 , L 씩 움직이게 된다.
그럼 코드로는 아래와 같이 만들 수 있다.
int N; // 맵의 가로,세로 크기
int L = pow(2,l); // 입력받은 l을 2^l 연산을 함
// 가로 세로 모두 한번 움직일때마다 L만큼씩 움직임
for(int i = 0; i < N; i += L){
for(int j = 0; j < N; j += L){
// 각 부분 배열에서 실행할 로직...
}
}주어진 맵을 전체 탐색할 때 행과 열 모두 L씩 움직임으로써
마치 부분 배열인 것처럼 움직일 수 있다.
이처럼 각 부분배열을 갈랐으면 그 이중 반복문 안에서
그 부분 배열 안에서 실행시킬 기능을 작성시켜 주면 된다.
부분 배열 내에서 상하/좌우 반전
위와 같은 방법으로 부분 배열을 나타냈을 때,
효율적으로 부분 배열을 반전하는 코드를 생각해 본다.
어느 정도 수학적인 게 들어가다 보니 나는 이해하기 어렵더라..
아직도 이걸 어떻게 생각하지 싶다..
일단 알기 쉽도록 (0,0)에서 시작하는 부분 배열부터 보자.
정사각형의 중심을 기점으로
서로 세로로 대칭되는 점과 교환된다.
이를 코드로 구현해 보자.
// i와 j 전체 맵에서의 좌표
// 부분 배열을 전체 훑음
for(int x = i; x < i + size; x++){
for(int y = j; y < j + size; y++){
swap(map[x][y],map[x][size-1-y]);
}
}
이는 시작점이 (0,0) 일 때에만 적용된다.
크기가 size일 때 나올 수 있는 시작점은
(0, size), (0,2*size), (0,3*size).. (size,0), (size, size).. (2*size,0)(2*size)..
맵의 크기가 허용하는 한 엄청나게 많을 것이다.
그래서 이 size와 맵의 크기에 대해 적용해 보자.
(0,0) 일 때 swap(map [i][j], map [x][size-1-y])이다.
여기서 y열로 size만큼 이동하면?
(0, size) 부분 배열 전체를 훑는 것은 똑같다.
그렇기 때문에 map [x][y]는 그대로이다.
또한 부분 배열 위치가 바뀐다고 해서
세로 대칭 규칙이 바뀌는 것이 아니다.
그냥 size만큼 평행이동만 했을 뿐이다.
그러면 swap(map [x][y], map [size-1-y-size]만 해주면 될까?
그렇지 않다.
원래 있던 size에 평행이동이 적용되지 않았기 때문이다.
이게 무슨 소리냐면, y값은 평행이동으로 값이 더 높아졌는데
size는 그대로이기 때문에 음수가 나올 수 있다.
그렇기 때문에 움직인 만큼 더 높여줘야 한다.
x행도 size만큼 이동하는 경우(size,0)도 고려해야 할까?
위 그림에서 알 수 있듯 항상 x축은 동일하다.
최종적으로 swap(map [x][y],
map [size+위치 보정값-1-y-size]가 된다.
여기서 위치 보정값은 size-1-y가 기존과 똑같이 빼지기 위함이므로
부분 배열 전체의 시작위치를 의미한다.
그리고 임시 변수 cnt에 배수를 저장해 열이 바뀔 때마다
cnt를 더해주다가 행이 바뀌면 다시 0으로 초기화한다.
최종적으로 나온 코드는 아래와 같다.
이는 k = 2 일 때를 구현한 것이다.
void action2(int k, int l){
int size = pow(2,l);
int cnt = 0;
for(int i = 0; i < map.size(); i += size){
for(int j = 0; j < map.size(); j += size){
for(int x = i; x < i + size; x++){
for(int y = j; y < j + size/2; y++){
swap(map[x][y],map[x][j+size-1-y+cnt*size]);
}
}
cnt++;
}
cnt = 0;
}
}k = 1 일 때의 로직도 2번과 비슷하기 때문에
문제 구현 단계에서 다른 점만 따로 설명하겠다.
부분 배열 내에 90도 회전
다음은 좀 더 까다로운 회전에 대해 생각해 보겠다.
기본적인 세팅은 위와 같다.
맵 전체를 탐색하는데 size만큼 칸을 이동한다.
일단, 배열을 회전하다가 값이 덮어써져 잘못 저장되는 것을 방지하기 위해
맵을 복사 해서 값을 가져오는 것으로 하겠다.
L = 4(즉 레벨 = 2)이 주어지고 (0,0) 일 때부터 살펴보자.
지금 해야 하는 것은 오른쪽 방향으로 90도 돌리는 것이다.
오른쪽의 원리와 왼쪽의 그림을 종합적으로 고려해 보면,
(0,0)부터 (i, j)까지 순차적으로 탐색한다고 했을 때
map [j][size-i-1] = copy_map [i][j]이다.
이제 여기서 size만큼 움직이는 경우를 생각해 보자.
여기서는 x와 y가 모두 바뀌기 때문에
둘 다 바뀔 때를 고려해줘야 한다.
일단 y를 size만큼 이동한다면?(0, size)
맵 전체를 훑는 것은 마찬가지이기 때문에 i와 j값은 그대로이다.
초록색 선은 가장 1행이 90도 돌았을 때 위치하는 곳이다.
보면 알 수 있듯이
그냥 y좌표로 size만큼 평행이동하였다.
원래 위치에서
저 초록색 선의 위치를 찾으려면 어떻게 해야 할까?
그냥 원래의 위치에서 size만큼 더해주면 된다.
그렇기 때문에 map [j][size-i-1+size] = copy_map [i][j]
y를 k번 움직이면
k*size배수가 되기 때문에 최종 식은
map [j][size-i-1+k*size] = copy_map [i][j]
그렇다면 x값 즉, 행이동을 한다면?(size,0)
기존의 위치에서 x값이 그냥 +size만큼 된 것뿐이다.
원래의 위치에서 size만큼 이동하고 부분배열에서의 거리를 표현하기 위해서는
전체 맵의 x좌표에서 행이동한 size만큼을 더해줘야 한다.
map [j+size][size-i-1+보정값+size] = copy_map [i][j]
마찬가지로 행이동을 m번하면 m*size번이다.
map [j+m*size][size-i-1] = copy_map [i][j]
마지막 경우는 둘 다 움직이는 경우이다.
(size, size) 이런 경우, 두 경우를 합치는 것뿐만 아니라
한 축이 움직이면서 생기는 보정 값에 대한 처리가 필요하다.
x와 y축이 동시에 size만큼 움직이는 것이기 때문에
x축으로 size만큼 움직이는 것을 y축으로 size만큼 움직이는 것이다.
따라서 x축으로 size만큼 움직인 것을 빼 준 후 바꿔준다.
그 후 돌려준 다음 적용시켜줘야 한다.
x방향으로 size만큼 움직인 횟수에 대한 x, y 값을 gapX, gapY
y방향으로 size만큼 움직인 횟수를 cnt라고 한다면
map [j-size*gapY+size*cnt][size-i-1+gapY] = copy_map [i][j]
이런 식으로 풀면 된다.
위에서 한 것은 시계 방향으로 돌린 것이고 ,
반시계로 돌린 것도 비슷한 로직을 따르므로,
이는 코드에서 자세히 설명하겠다.
나머지 기능들은 위에서 설명한 로직 4개를 이용하면 쉽게 구할 수 있기 때문에
문제 구현 단계에서 바로 설명하겠다.
문제 구현 단계
// 상하 반전
void action1(int k, int l){
int size = pow(2,l); // 부분 배열 길이
int cnt = 0; // 현재 진행한 횟수
// size 크기만큼 더함
for(int i = 0; i < map.size(); i += size){
for(int j = 0; j < map.size(); j += size){
// swap하기 때문에 가로의 절반만큼만 진행
for(int x = i; x < i + size/2; x++){
for(int y = j; y < j + size; y++){
// 위에서 세웠던 식
swap(map[x][y],map[i+size-1-x+cnt*size][y]);
}
}
}
// 가로가 바뀔때마다 이므로
cnt++; // 횟수 + 1
}
}
// 좌우 반전
void action2(int k, int l){
int size = pow(2,l);
int cnt = 0;
for(int i = 0; i < map.size(); i += size){
for(int j = 0; j < map.size(); j += size){
for(int x = i; x < i + size; x++){
// 이번에는 세로의 절반 만큼만
for(int y = j; y < j + size/2; y++){
swap(map[x][y],map[x][j+size-1-y+cnt*size]);
}
}
cnt++; // 좌우 반전이기 때문에 세로가 바뀔때마다 cnt+1
}
cnt = 0; // 행이 바뀌면 초기화해줘야함
}
}기능 1,2를 만든 함수이다.
부분 배열의 크기를 뜻하는 size만큼 전체 맵의 탐색을 한다.
1번과 2번 모두 swap을 사용하여 두 위치를 바꾸기 때문에
모든 부분이 아닌 딱 절반씩만 탐색한다.
두 함수의 차이점은
더해지는 cnt의 위치가 서로 다르다는 것인데,
상하 반전일 때는 전체 맵의 행이 바뀔 때, 즉 가로로 size가 더해질 때이고,
좌우 반전일 때는 전체 맵의 열이 바뀔 때, 즉 세로로 size가 더해질 때이다.
이때는 행이 바뀌면 다시 cnt=0으로 초기화해줘야 한다.
// 시계 방향 회전
void action3(int k, int l){
int size = pow(2,l);
if(size == 1) return; // 사이즈 1이면 안돌아감
vector<vector<int>> tmp = map; // 배열 복사
int cnt = 0; // 전체 맵의 행 보정값
int gapX = 0; // 부분 배열의 X보정값
int gapY = 0; // 부분 배열의 Y보정값
int squareX, squareY;
for(int i = 0; i < map.size(); i += size){
for(int j = 0; j < map.size(); j += size){
squareX = i + size;
squareY = j + size;
for(int n = i; n < squareX; n++){
for(int m = j; m < squareY; m++){
map[m-size*gapX+size*cnt][squareX-n-1 + size* gapY] = tmp[n][m];
}
}
gapX++;
gapY++;
}
// 맵이 바뀌었기 때문에 초기화
gapX = 0;
gapY = 0;
cnt++;
}
}
// 반시계 방향
void action4(int k, int l){
int size = pow(2,l);
if(size == 1) return;
vector<vector<int>> tmp = map;
int cnt = 0;
int gapX = 0;
int gapY = 0;
int squareX, squareY;
for(int i = 0; i < map.size(); i += size){
for(int j = 0; j < map.size(); j += size){
squareX = i + size;
squareY = j + size;
for(int n = i; n < squareX; n++){
for(int m = j; m < squareY; m++){
map[squareY-m-1+size*gapX][n + size* gapY- size* cnt] = tmp[n][m];
}
}
// x방향으로는 더해주지 않음
gapY++;
}
// x갭은 이떼 더해줌
// 반시계이기 때문에 이때 더해짐
gapX++;
gapY = 0; // y갭은 초기화
cnt++;
}
}같은 부분 배열 내에서 시계/반시계 방향으로 90도 회전시키는 함수인데,
이건 좀 복잡하다.
배열 복사를 하고, 보정 값을 위한 다양한 변수들이 쓰이는데,
일단 위에서 세웠던 식은 설명을 생략하겠다.
그 아래에 gapX++ gapY++은 어느 정도 이해 갈 것이다.
근데 가장 이해가지 않는 것은 반시계 방향일 때
왜 gapY만 더해주고 gapX는 더해주지 않을까?
그리고 전체 맵의 행이 더해질 때
왜 gapX가 더해지고 gapY는 초기화될까?
이는 반시계 방향으로 움직이기 때문에 그렇다.
반시계로 움직이기 때문에
애초에 가장 첫 번째 행부터 쌓이기 때문에 보정값이 필요 없다.
그래서 거기서부터 쌓아주고
행이 바뀔 때마다 한 칸씩 더해주면 되는 것이다.
// 배열끼리 상하반전
void action5(int k, int l){
int size = pow(2,l);
action1(1,N);
action1(1,l);
/*
전체 배열을 상하반전 시킨 후,
l 부분 배열 내에서 다시 90도 돌리면
배열끼리 상하반전 한거랑 똑같음
*/
}
// 배열끼리 좌우 반전
void action6(int k, int l){
action2(2,N);
action2(1,l);
/*
위 설명과 비슷
*/
}
// 배열끼리 시계 방향 90도
void action7(int k, int l){
action3(3,N);
action4(4,l);
/*
전체 배열을 시계 방향으로 90도 돌린 후,
부분 배열 l 내에서 다시 반시계 방향으로 90도 돌림
배열끼리 시계 방향 90도 돌린거랑 똑같음
*/
}
// 배열끼리 반시계 방향 90도
void action8(int k, int l){
action4(4,N);
action3(3,l);
/*
위와 비슷한 설명
*/
}위 함수는 기능 5,6,7,8인데 사실 기능 1,2,3,4들을 사용하여
나머지 기능들을 구현할 수 있다.
원리들은 주석으로 달아놨기 때문에 충분히 이해가능하리라 생각한다.
아래에는 이제 전체 코드를 올리고 마무리하겠다.
#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
vector<vector<int>> map;
int N,R;
void action1(int k, int l){
int size = pow(2,l);
int cnt = 0;
for(int i = 0; i < map.size(); i += size){
for(int j = 0; j < map.size(); j += size){
for(int x = i; x < i + size/2; x++){
for(int y = j; y < j + size; y++){
swap(map[x][y],map[i+size-1-x+cnt*size][y]);
}
}
}
cnt++;
}
}
void action2(int k, int l){
int size = pow(2,l);
int cnt = 0;
for(int i = 0; i < map.size(); i += size){
for(int j = 0; j < map.size(); j += size){
for(int x = i; x < i + size; x++){
for(int y = j; y < j + size/2; y++){
swap(map[x][y],map[x][j+size-1-y+cnt*size]);
}
}
cnt++;
}
cnt = 0;
}
}
// 시계 방향 회전
void action3(int k, int l){
int size = pow(2,l);
if(size == 1) return; // 사이즈 1이면 안돌아감
vector<vector<int>> tmp = map; // 배열 복사
int cnt = 0; // 전체 맵의 행 보정값
int gapX = 0; // 부분 배열의 X보정값
int gapY = 0; // 부분 배열의 Y보정값
int squareX, squareY;
for(int i = 0; i < map.size(); i += size){
for(int j = 0; j < map.size(); j += size){
squareX = i + size;
squareY = j + size;
for(int n = i; n < squareX; n++){
for(int m = j; m < squareY; m++){
map[m-size*gapX+size*cnt][squareX-n-1 + size* gapY] = tmp[n][m];
}
}
gapX++;
gapY++;
}
// 맵이 바뀌었기 때문에 초기화
gapX = 0;
gapY = 0;
cnt++;
}
}
// 반시계 방향
void action4(int k, int l){
int size = pow(2,l);
if(size == 1) return;
vector<vector<int>> tmp = map;
int cnt = 0;
int gapX = 0;
int gapY = 0;
int squareX, squareY;
for(int i = 0; i < map.size(); i += size){
for(int j = 0; j < map.size(); j += size){
squareX = i + size;
squareY = j + size;
for(int n = i; n < squareX; n++){
for(int m = j; m < squareY; m++){
map[squareY-m-1+size*gapX][n + size* gapY- size* cnt] = tmp[n][m];
}
}
// x방향으로는 더해주지 않음
gapY++;
}
// x갭은 이떼 더해줌
// 반시계이기 때문에 이때 더해짐
gapX++;
gapY = 0; // y갭은 초기화
cnt++;
}
}
// 배열끼리 상하반전
void action5(int k, int l){
int size = pow(2,l);
action1(1,N);
action1(1,l);
/*
전체 배열을 상하반전 시킨 후,
l 부분 배열 내에서 다시 90도 돌리면
배열끼리 상하반전 한거랑 똑같음
*/
}
// 배열끼리 좌우 반전
void action6(int k, int l){
action2(2,N);
action2(1,l);
/*
위 설명과 비슷
*/
}
// 배열끼리 시계 방향 90도
void action7(int k, int l){
action3(3,N);
action4(4,l);
/*
전체 배열을 시계 방향으로 90도 돌린 후,
부분 배열 l 내에서 다시 반시계 방향으로 90도 돌림
배열끼리 시계 방향 90도 돌린거랑 똑같음
*/
}
// 배열끼리 반시계 방향 90도
void action8(int k, int l){
action4(4,N);
action3(3,l);
/*
위와 비슷한 설명
*/
}
int main(){
scanf("%d %d",&N,&R);
map.resize(pow(2,N),vector<int>(pow(2,N),0));
for(int i = 0; i < pow(2,N); i++)
for(int j = 0; j < pow(2,N); j++) cin >> map[i][j];
while(R--){
int k,l;
scanf("%d %d",&k, &l);
switch(k){
case 1 : action1(k,l);
break;
case 2 : action2(k,l);
break;
case 3 : action3(k,l);
break;
case 4 : action4(k,l);
break;
case 5 : action5(k,l);
break;
case 6 : action6(k,l);
break;
case 7 : action7(k,l);
break;
case 8 : action8(k,l);
break;
}
}
for(int i = 0; i < map.size(); i++){
for(int j = 0; j < map.size(); j++) printf("%d ",map[i][j]);
printf("\n");
}
}
시행착오
이 문제는 상당히 구현할 것도 많긴 한데, 복잡하기까지 했다.
배열들을 수학적으로 다뤄야 하는 문제여서,
풀이를 봐도 전혀 이해가 되지 않았다.
이해하는 데만 며칠이 걸렸으며, 지금도 확실하게 이해되진 않는다.
이런 문제가 다시 나온다면 맞출 자신이 없다.
최대한 많이 구현해 보는 게 답일까? 아니며 넘기는 게 답일까?