백준 16926 배열 돌리기 1

• 백준 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번 회전시킨 결과를 구해보자.

풀이

실버 5이지만 꽤 어렵다. 잘 구현해야 시간 초과가 안나온다.

1. 한번 회전할때, 몇 번 돌려야 하는지 계산해야한다.

예를들어 6 x 8 행렬이 있을 때 회전 시키는 그룹은 아래와 같이 나뉘고, 그룹은 3개이다.

4 x 3 행렬일땐 그룹은 2개이다.

이런식으로 그림을 그리다 보면 한번 회전할때 n X m 행렬에서 min(n, m) / 2개의 그룹을 반시계 방향으로 돌려야 한다는 결론이 나온다.

2. 어떻게 반시계 방향으로 돌리지??

dfs나 while문을 잘써서 돌리면 된다.

// y, x : 현재좌표 d: 현재 방향 l: arr[y][x]에 넣어줄 값, c는 현재 그룹
			//남,동,북,서
int dy[4] = { 1,0,-1,0 }; 
int dx[4] = { 0,1,0,-1 };

void dfs(int y, int x, int d, int l,int c) 
{
	int cur = arr[y][x];
	arr[y][x] = l;
	int ny = y + dy[d];
	int nx = x + dx[d];
	if (d == 3 && (ny == c && nx == c)) return;	// 다 돌면
	if (ny >= c && ny < N - c && nx >= c && nx < M - c && !(ny==c && nx==c)) {
		dfs(ny, nx, d, cur, c);	// 계속 진행할 수 있으면
	}
	else if (d + 1 < 4) {	// 서쪽으로 진행하는 중이 아니고, 더이상 진행할 수 없으면 방향을 바꾼다.
		ny = y + dy[d + 1];
		nx = x + dx[d + 1];
		if (d == 3 && (ny == c && nx == c)) return;
		dfs(ny, nx, d + 1, cur, c);
	}	
}

예를 들어 위의 그림처럼 y가 0, x가 2인 경우엔 l은 바로 이전의 1이고 c는 제일 바깥 그룹이라 0 이다.
방향은 arr[0][0]부터 반시계 방향으로 해서 남 -> 동 -> 북 -> 서 쪽으로 갈것이고 d로 표현해주었다.

전체코드는 아래와 같다.

#include <iostream>
#define MAX 301

using namespace std;

int N, M, R;
int arr[MAX][MAX];

int dy[4] = { 1,0,-1,0 }; 
int dx[4] = { 0,1,0,-1 };

void dfs(int y, int x, int d, int l,int c) 
{
	int cur = arr[y][x];
	arr[y][x] = l;
	int ny = y + dy[d];
	int nx = x + dx[d];
	if (d == 3 && (ny == c && nx == c)) return;
	if (ny >= c && ny < N - c && nx >= c && nx < M - c && !(ny==c && nx==c)) {
		dfs(ny, nx, d, cur, c);
	}
	else if(d + 1 < 4){
		ny = y + dy[d + 1];
		nx = x + dx[d + 1];
		if (d == 3 && (ny == c && nx == c)) return;
		dfs(ny, nx, d + 1, cur,c);
	}	
}

int main(void) 
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin >> N >> M >> R;
	for (int i = 0; i < N; ++i) {
		for (int j = 0; j < M; ++j) {
			cin >> arr[i][j];
		}
	}
	
	int s = 0;	// 그룹의 수
	if (N < M) s = N / 2;
	else s = M / 2;
	
	while (R--) {	
		for (int i = 0; i < s; ++i) {
			dfs(i, i, 0, arr[i][i + 1], i);
		}
	}
	
	for (int i = 0; i < N; ++i) {
		for (int j = 0; j < M; ++j) {
			cout << arr[i][j] << " ";
		}
		cout << "\n";
	}
	return 0;
}

구현 연습하기 좋은 문제인것같다. 이 문제가 다가 아니라 시리즈로 있어서 다 풀어보면 좋을 것 같다.

비슷한 문제

• 백준 16927 - 배열 돌리기2