[backjoon]16927 배열돌리기2 java

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

16927번: 배열 돌리기 2

요청 사항에 따라 배열을 돌리는 문제!

나는 이런 배열을 돌리는 문제에서 주로 Deque를 이용해서 문제 풀이를 한다.

돌리는 방향에 맞게 for문 4개를 이용해서 순서에 맞게 해당 값을 모두 queue에 넣어준다.

이동하는 횟수에 맞게 앞의 값을 뒤로 다시 넣어줌으로써 순서를 맞춰준다.

이후 처음 값을 가져온 순서대로 다시 값을 넣어준다.

이 문제는 값이 매우 커서 시간 초과가 나기 쉬운데 R번 반복해서 회전 시키는 것이 아니라 R개의 칸을 한 꺼번에 이동하는 개념으로 가야한다. ...1)

또한, 사이클이 생길 수 있기 때문에 불필요한 회전을 줄이기 위해 해당 칸 만큼만 이동할 수 있도록 나머지 연산자를 활용하였다....2)

이 문제는 거기에 DFS를 이용해서 반복을 해줘야하는데 점점 가로/세로의 각각 끝점이 가까워지는 것을 이용하여 값이 역전되면 종료되도록 하였다.

 

import java.io.*;
import java.util.*;

class Main {
	static int[][] map;
	static int N, M, R;

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		st = new StringTokenizer(br.readLine());

		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		R = Integer.parseInt(st.nextToken());
		map = new int[N][M];
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < M; j++) {
				int cur = Integer.parseInt(st.nextToken());
				map[i][j] = cur;
			}
		}
        
		dfs(0, N - 1, 0, M - 1);

		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				System.out.print(map[i][j] + " ");
			}
			System.out.println();
		}
	}

	public static void dfs(int x1, int x2, int y1, int y2) {

		//양 끝 값이 역전되는 순간 종료!
		if (x1 > x2 || y1 > y2) return;
		
		Deque<Integer> queue = new LinkedList<>();
		for (int i = x1; i < x2; i++) {
			queue.add(map[i][y1]);
		}
		for (int i = y1; i < y2; i++) {
			queue.add(map[x2][i]);
		}
		for (int i = x2; i > x1; i--) {
			queue.add(map[i][y2]);
		}
		for (int i = y2; i > y1; i--) {
			queue.add(map[x1][i]);
		}
		
		//1)과 2)
        //1) R번 회전하되, 2) 불필요한 회전을 안 하기 위해 size보다 작은 수로 회전하도록 한다.
		int r = R %queue.size();
		while (r-- > 0) {
			int temp = queue.pollLast();
			queue.addFirst(temp);
		}

		for (int i = x1; i < x2; i++) {
			map[i][y1] = queue.poll();
		}
		for (int i = y1; i < y2; i++) {
			map[x2][i] = queue.poll();
		}
		for (int i = x2; i > x1; i--) {
			map[i][y2] = queue.poll();
		}
		for (int i = y2; i > y1; i--) {
			map[x1][i] = queue.poll();
		}
		
		
		//양 끝점의 값을 한 칸씩 이동하여 범위를 재지정해준다.
		dfs(x1 + 1, x2 - 1, y1 + 1, y2 - 1);

	}
}