백준(BOJ) 16926번 배열 돌리기 1

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

16926번: 배열 돌리기 1

 

풀이 :

 

재귀적으로 배열이 끝에서만 돌도록 구현해보았다.

 

중요한 것은 wall을 기준으로 wall이 0,0일 때 1,1일 때 2,2일 때를 정하여 왼쪽 위를 기준으로 한 바퀴를 돌리는 것이다.

 

wall의 횟수는 가로와 세로중 짧은 변의 길이를 나누기 2할 수만큼 회전하면 된다.

 

calcWall는 wall이 0이라면 0,0을 기준으로 끝에서만 돌도록 해 주고  1이라면 1,1을 기준으로 돌도록 구현한 것이다.

 

 

코드가 좀 지져분해 졌는데 조금 더 깔끔하고 빠르게 짜도록 더 연습해야겠다.

 

코드 ( C++ )

 

	#include <iostream>
	#include <vector>
	#include <queue>
	#include <algorithm>
	using namespace std;
	int n, m, r;
	vector<vector<int>> board;
	bool visited[301][301];
	const int dy[4] = { 1,0,-1,0 };
	const int dx[4] = { 0, 1, 0, -1 };
	bool calcWall(int y, int x, int wall)
	{
	return ((y == wall || y == n - wall - 1) ||
	(y != wall && x == wall || y != wall && x == m - wall - 1));
	}
	void rotate(vector<vector<int>>& v, int y, int x, int next, int cur, int wall)
	{
	if (y + 1 < n && !visited[y + 1][x] && calcWall(y+1,x,wall)) {
	next = v[y + 1][x];
	v[y + 1][x] = cur;
	visited[y + 1][x] = true;
	cur = next;
	rotate(v, y + 1, x, next, cur, wall);
	return;
	}
	if (x + 1 < m && !visited[y][x + 1] && calcWall(y , x+1, wall)) {
	next = v[y][x + 1];
	v[y][x + 1] = cur;
	visited[y][x + 1] = true;
	cur = next;
	rotate(v, y, x + 1, next, cur, wall);
	return;
	}
	if (y - 1 >= 0 && !visited[y - 1][x] && calcWall(y - 1, x, wall)) {
	next = v[y - 1][x];
	v[y - 1][x] = cur;
	visited[y - 1][x] = true;
	cur = next;
	rotate(v, y - 1, x, next, cur, wall);
	return;
	}
	if (x - 1 >= 0 && !visited[y][x - 1] && calcWall(y, x-1, wall)) {
	next = v[y][x - 1];
	v[y][x - 1] = cur;
	visited[y][x - 1] = true;
	cur = next;
	rotate(v, y, x - 1, next, cur, wall);
	return;
	}
	}
	int main()
	{
	cin >> n >> m >> r;
	board = vector<vector<int>>(n, vector<int>(m, 0));
	for (int i = 0; i < n; ++i)
	for (int j = 0; j < m; ++j)
	{
	cin >> board[i][j];
	}
	int len = n > m ? m/2 : n/2;
	int cnt = 0;
	while (cnt < r) {
	for (int wall = 0; wall < len; ++wall) {
	rotate(board, wall, wall, 0, board[wall][wall], wall);
	}
	memset(visited, 0, sizeof(visited));
	cnt++;
	}
	for (int i = 0; i < n; ++i) {
	for (int j = 0; j < m; ++j)
	cout << board[i][j] << " ";
	cout << "\n";
	}
	return 0;
	}

view raw .cpp hosted with ❤ by GitHub