[Java Algorithm] 배열 돌리기 2 BOJ #16927

문제

https://www.acmicpc.net/problem/16927

16927번: 배열 돌리기 2

 

내 문제 풀이

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
	
	static int[][] nums;
	static int n, m, r;
	static int[] dx = {0, 1, 0, -1};
	static int[] dy = {1, 0, -1, 0};
	static int nNext, mNext; // 띠마다 줄어드는 변의 길이 저장을 위함
	
	public static void turn(int start, int nowTurnNum) {
		for(int i = 0; i < nowTurnNum ; i++) { // 유효 회전 수 만큼만 회전
			int x = start;
			int y = start;
			int tmp = nums[start][start];
			int dir = 0; // 범위를 벗어날 때마다 dir을 바꿔주어 방향 전환
			
			while(dir < 4) {
				int nx = x + dx[dir];
				int ny = y + dy[dir];
				
				if(nx < start || ny < start || nx >= n-start || ny >= m-start) { // 범위 벗어날 시 방향 전환
					dir++; 
					continue;
				}
				
				nums[x][y] = nums[nx][ny];
				x = nx;
				y = ny;
			}
			
			nums[start+1][start] = tmp;
		}
	}

	public static void main(String[] args) throws Exception {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		StringBuffer out = new StringBuffer();
		
		st = new StringTokenizer(in.readLine());
		n = Integer.parseInt(st.nextToken());
		m = Integer.parseInt(st.nextToken());
		nNext = n;
		mNext = m;
		r = Integer.parseInt(st.nextToken());
		int turnNum = Math.min(n, m) / 2; // 회전시켜야 하는 띠의 개수
		nums = new int[n][m];
		
		for(int i = 0; i < n; i++) {
			st = new StringTokenizer(in.readLine());
			for(int j = 0; j < m; j++) nums[i][j] = Integer.parseInt(st.nextToken());
		}
		
		for(int i = 0; i < turnNum; i++) { // 내부로 들어가면서 모든 띠 순회
			turn(i, r % ((nNext + mNext - 2) * 2));
			nNext -= 2;
			mNext -= 2;
		}
		
		for(int i = 0; i < n; i++) {
			for(int j = 0; j < m; j++) {
				out.append(nums[i][j]);
				if(j < m-1) out.append(" ");
			}
			out.append("\n");
		}
		System.out.println(out);
	}

}

👉 구현 문제

 

[ 로직 설명 ]

✔️ 회전하는 배열은 가장 바깥에서부터 안쪽으로 한 칸씩의 띠를 형성하고,
같은 띠들이 함께 그룹을 형성하여 회전한다고 생각하면 된다.

 

✔️ 나는 하나의 띠마다 가장 좌측 상단을 꼭짓점으로 보고, 꼭짓점에 저장된 값을 tmp에 넣어놓은 뒤
왼쪽에서부터 하나씩 자리를 옮겨주는 식으로 배열을 회전시켰다.

 

✔️ 그런데 여기서 중요한 점은, 이와 비슷한 #16926번 문제의 경우 진짜 회전만 시켜도 괜찮다.
하지만 이 문제는 주어진 회전에 대한 입력 범위가 아주 커졌고, 효율이 관건이다.

 

✔️ 따라서 나는 아주 많이 회전하게 될 경우 생길 수 있는 중복된 회전을 피하고자 했다.
예를 들어 위 그림 배열의 가장 바깥 쪽 띠는 12번 회전 시 원상복구되어 회전의 의미가 없다.
=> 14번 회전하라고 주어진다면 그 중 12번을 제외한 2번만 회전하여도 같은 결과를 얻을 수 있다.

 

✔️ 이에 나는 띠마다 유효한 회전 수에 대한 점화식을 구하였다.
띠마다 원상복귀되는 회전 수 : (세로 길이 + 가로 길이 - 2) * 2
=> 띠마다 유효한 회전 수 : R % ((세로 길이 + 가로 길이 - 2) * 2

 

 

💡 피드백

• 너무너무 헷갈리는 문제였다. 배열 돌리기 시리즈를 풀어보는 중인데,
  꽤 풀기 어지러운 문제들이지만,, 확실히 도움이 될 것 같긴하다.
  문제집: 배열 돌리기 (시리즈) (acmicpc.net)