백준 16926 배열 돌리기 1 c++ (구현)

문제 출처 : https://www.acmicpc.net/problem/16926

16926번: 배열 돌리기 1

문제

크기가 N×M인 배열이 있을 때, 배열을 돌려보려고 한다. 배열은 다음과 같이 반시계 방향으로 돌려야 한다.

A[1][1] ← A[1][2] ← A[1][3] ← A[1][4] ← A[1][5]
   ↓                                       ↑
A[2][1]   A[2][2] ← A[2][3] ← A[2][4]   A[2][5]
   ↓         ↓                   ↑         ↑
A[3][1]   A[3][2] → A[3][3] → A[3][4]   A[3][5]
   ↓                                       ↑
A[4][1] → A[4][2] → A[4][3] → A[4][4] → A[4][5]

예를 들어, 아래와 같은 배열을 2번 회전시키면 다음과 같이 변하게 된다.

1 2 3 4       2 3 4 8       3 4 8 6
5 6 7 8       1 7 7 6       2 7 8 2
9 8 7 6   →   5 6 8 2   →   1 7 6 3
5 4 3 2       9 5 4 3       5 9 5 4
 <시작>         <회전1>        <회전2>

배열과 정수 R이 주어졌을 때, 배열을 R번 회전시킨 결과를 구해보자.

입력

첫째 줄에 배열의 크기 N, M과 수행해야 하는 회전의 수 R이 주어진다.

둘째 줄부터 N개의 줄에 배열 A의 원소 Aij가 주어진다.

출력

입력으로 주어진 배열을 R번 회전시킨 결과를 출력한다.

제한

• 2 ≤ N, M ≤ 300
• 1 ≤ R ≤ 1,000
• min(N, M) mod 2 = 0
• 1 ≤ Aij ≤ 108

알고리즘 분류

• 구현

풀이

이번 하반기 코테에 배열을 돌리는 문제가 3번 정도 나온 것 같다.

이런 문제들은 다른 방법이 없다. 그냥 풀어보고, 연습해야 한다.

이 문제는 그래프의 테두리에서부터 중앙까지 depth를 계산해서 인덱스를 다룰 수 있다.

n과 m중 작은 값을 2로 나눈 값과 n과 m중 작은 값을 2로 나눈 나머지를 더하면 그래프 탐색의 뎁스가 된다.

이후, 시작점의 좌표를 0~depth-1로 두고, 뎁스 별로 한 바퀴씩 삥 돌며 값들을 바꿔주면 된다.

코드

#include <iostream>
#include <algorithm>
using namespace std;

//2<=n,m<=300
//1<=t<=1000
//min(n,m)mod2=0
//1<=aij<=10^8
int n, m, t;
int graph[300][300];

void dfs(int t) {
	if (t == 0) return;
	int depth = min(n, m) / 2 + min(n, m) % 2;
	for (int start = 0; start < depth; start++) {
		int r = start;
		int c = start;
		int pre =graph[r][c];
		//왼쪽
		while (r < n - 1 - start) {
			int nextVal = graph[r + 1][c];
			graph[r + 1][c] = pre;
			pre = nextVal;
			r++;
		}
		//바닥
		while (c < m-1-start) {
			int nextVal = graph[r][c + 1];
			graph[r][c + 1] = pre;
			pre = nextVal;
			c++;
		}
		//오른쪽
		while (r>=1+start) {
			int nextVal = graph[r - 1][c];
			graph[r - 1][c] = pre;
			pre = nextVal;
			r--;
		}
		//위
		while (c>=1+start) {
			int nextVal = graph[r][c - 1];
			graph[r][c - 1] = pre;
			pre = nextVal;
			c--;
		}
	}
	dfs(t - 1);

}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> n >> m >> t;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> graph[i][j];
		}
	}
	dfs(t);
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cout << graph[i][j]<<' ';
		}
		cout << '\n';
	}
	return 0;
}