백준 / 배열 돌리기 6 - 부분 배열 반전, 회전 / C++

*문제 출처는 백준에 있습니다.

문제 제목: 배열 돌리기 6

문제 사이트: https://www.acmicpc.net/problem/20327

---

* 풀다가 전역 변수 관리 잘못해서 출력이 안나오기도 했었다.. 꼭 전역변수 / 지역변수 구분해서 잘 코딩하기

이 문제는 상하좌우 반전, 회전은 기본으로 풀 수 있을때 푸는게 좋다.

 

 

나의 풀이

#include<stdio.h>
#define MAX 200
// 부분 배열 내에서의 연산
#define FLIP_UPDOWN (1)
#define	FLIP_LEFTRIGHT (2)
#define ROTATE_RIGHT (3)
#define ROTATE_LEFT (4)

// 부분 배열 자체를 한 칸으로 
#define SPLIT_FLIP_UPDOWN (5)
#define SPLIT_FLIP_LEFTRIGHT (6)
#define SPLIT_ROTATE_RIGHT (7)
#define SPLIT_ROTATE_LEFT (8)

int MAP[MAX][MAX];
int temp[MAX][MAX];
int N, R, N2;


void input() {
	scanf("%d %d", &N, &R);
	N2 = 1 << N;
	for (int r = 0; r < N2; r++) {
		for (int c = 0; c < N2; c++) {
			scanf("%d", &MAP[r][c]);
		}
	}
	
}

void printMAP(int origin[MAX][MAX]) {
	for (int r = 0; r < N2; r++) {
		for (int c = 0; c < N2; c++) {
			printf("%d ", origin[r][c]);
		}
		putchar('\n');
	}
}

// 부분 사각형에서 상하 반전
void flipUpdownSize(int sr, int sc, int size) {
	// 부분 사각형 복사
	for (int r = 0; r < size; r++) {
		for (int c = 0; c < size; c++) {
			temp[r][c] = MAP[sr + r][sc + c];
		}
	}

	// 부분 사각형 상하 반전
	for (int r = 0; r < size; r++) {
		for (int c = 0; c < size; c++) {
			MAP[sr + r][sc + c] = temp[size - 1 - r][c];
		}
	}
}

void flipUpdown(int level) {
	int size = 1 << level; // 부분 직사각형 변의 길이
	
	for (int sr = 0; sr < N2; sr += size) {
		for (int sc = 0; sc < N2; sc += size) {
			flipUpdownSize(sr, sc, size);
		}
	}
}


// 부분 사각형에서 좌우 반전
void flipLeftRightSize(int sr, int sc, int size) {
	// 부분 사각형 복사
	for (int r = 0; r < size; r++) {
		for (int c = 0; c < size; c++) {
			temp[r][c] = MAP[sr + r][sc + c];
		}
	}

	// 부분 사각형 상하 반전
	for (int r = 0; r < size; r++) {
		for (int c = 0; c < size; c++) {
			MAP[sr + r][sc + c] = temp[r][size - 1 - c];
		}
	}
}

void flipLeftRight(int level) {
	int size = 1 << level; // 부분 직사각형 변의 길이

	for (int sr = 0; sr < N2; sr += size) {
		for (int sc = 0; sc < N2; sc += size) {
			flipLeftRightSize(sr, sc, size);
		}
	}
}

void rotate_rightSize(int sr, int sc, int size) {
	// 부분 사각형 복사
	for (int r = 0; r < size; r++) {
		for (int c = 0; c < size; c++) {
			temp[r][c] = MAP[sr + r][sc + c];
		}
	}

	// 부분 사각형 오른쪽으로 90도 회전
	for (int r = 0; r < size; r++) {
		for (int c = 0; c < size; c++) {
			MAP[sr + r][sc + c] = temp[size-1-c][r];
		}
	}
}

void rotate_leftSize(int sr, int sc, int size) {
	// 부분 사각형 복사
	for (int r = 0; r < size; r++) {
		for (int c = 0; c < size; c++) {
			temp[r][c] = MAP[sr + r][sc + c];
		}
	}

	// 부분 사각형 오른쪽으로 90도 회전
	for (int r = 0; r < size; r++) {
		for (int c = 0; c < size; c++) {
			MAP[sr + r][sc + c] = temp[c][size-1-r];
		}
	}
}


void rotate_right(int level) {
	int size = 1 << level; // 부분 직사각형 변의 길이

	for (int sr = 0; sr < N2; sr += size) {
		for (int sc = 0; sc < N2; sc += size) {
			rotate_rightSize(sr, sc, size);
		}
	}
}

void rotate_left(int level) {
	int size = 1 << level; // 부분 직사각형 변의 길이

	for (int sr = 0; sr < N2; sr += size) {
		for (int sc = 0; sc < N2; sc += size) {
			rotate_leftSize(sr, sc, size);
		}
	}
}

void split_updown(int level) {
	// 전체를 위아래로 뒤집고
	flipUpdown(N);

	// 부분 배열만 다시 뒤집는다 (그러면 부분 배열의 안의 값은 반전이 되지 않음)
	flipUpdown(level);
}

void split_leftright(int level) {
	flipLeftRight(N);
	flipLeftRight(level);
}

void split_rotate_right(int level) {
	rotate_right(N);
	rotate_left(level);
}

void split_rotate_left(int level) {
	rotate_left(N);
	rotate_right(level);
}
int main() {
	input();
	
	
	for (int r = 0; r < R; r++) {
		int k, level;
		scanf("%d %d", &k, &level);

		if (k == FLIP_UPDOWN) flipUpdown(level);
		else if (k == FLIP_LEFTRIGHT) flipLeftRight(level);
		else if (k == ROTATE_RIGHT) rotate_right(level);
		else if (k == ROTATE_LEFT) rotate_left(level);
		else if (k == SPLIT_FLIP_UPDOWN) split_updown(level);
		else if (k == SPLIT_FLIP_LEFTRIGHT) split_leftright(level);
		else if (k == SPLIT_ROTATE_RIGHT) split_rotate_right(level);
		else if (k == SPLIT_ROTATE_LEFT) split_rotate_left(level);

	}
	printMAP(MAP);
	

	return 0;
}

 

K = 1 / 2 / 3 / 4

 

level 이 문제에서의 입력값 ℓ 를 뜻할때,

각 부분 직사각형의 한 변의 길이를 

int size = 1 << level;

로 정의하면,

 

만약 ℓ  = level = 3, 부분 사각형의 한변의 길이는 1 << 3 이므로

1<< 3 은 8이다.

 

따라서 부분 사각형의 한 변의 길이는 8이 된다.

 

연산을 할 때, 각각 시작 지점의 좌표 sr, sc 와 부분 사각형의 한 변의 길이만 안다면 해당 범위 내부에서의 배열을 탐색할 수 있다.

 

예시 )

void rotate_right(int level) {
	int size = 1 << level; // 부분 직사각형 변의 길이

	for (int sr = 0; sr < N2; sr += size) {
		for (int sc = 0; sc < N2; sc += size) {
			rotate_rightSize(sr, sc, size);
		}
	}
}

 

이렇게 부분 사각형의 시각 지점마다 연산을 진행하게 되면 아래와 같이 rotate 를 진행해준다.

void rotate_rightSize(int sr, int sc, int size) {
	// 부분 사각형 복사
	for (int r = 0; r < size; r++) {
		for (int c = 0; c < size; c++) {
			temp[r][c] = MAP[sr + r][sc + c];
		}
	}

	// 부분 사각형 오른쪽으로 90도 회전
	for (int r = 0; r < size; r++) {
		for (int c = 0; c < size; c++) {
			MAP[sr + r][sc + c] = temp[size-1-c][r];
		}
	}
}

부분 배열 내부에서의 회전 및 반전 연산을 해야하기때문에 부분배열만 복사하여 각각 연산을 진행한다.

 

K = 5, 6, 7, 8

부분 배열을 제외하고 큰 틀(??) 들만 연산을 진행하므로

부분 배열 내부의 값은 바뀌면 안된다.

 

이때, 사각형 전체에 대해 연산을 진행하고,

부분 배열 내부의 수들을 다시 반대로 연산을 진행하면 부분배열만 연산이 안된것처럼 보인다.

 

 

예를 들어서 상하반전을 한다고 하자,

전체 사각형을 반전하고

부분 배열들을 다시 반전하게 된다면 전체 배열의 위치는 바뀌지만,

부분 배열 내부에서는 반전이 일어나지 않은 것 처럼 연산이 된다.

 

예시

void split_updown(int level) {
	// 전체를 위아래로 뒤집고
	flipUpdown(N);

	// 부분 배열만 다시 뒤집는다 (그러면 부분 배열의 안의 값은 반전이 되지 않음)
	flipUpdown(level);
}

이런식으로 나머지 연산들에대해서도 동일하게 해준다.