[Java] 백준 16926번 배열 돌리기 1 with 자바

: ) YOUNG·2022년 5월 11일
2

알고리즘

목록 보기
127/417
post-thumbnail

문제

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


크기가 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]


생각하기

이전에 풀었던 프로그래머스의 행렬 회전 문제와 아주 흡사하지만, 내부 회전을 하는 걸로 봤을 때, 뭔가 이게 더 조금 어려운 느낌이었다.

그때의 로직과 크게 바뀌지 않았다.
배열을 회전시키고 회전시키전에 이전에 있었던 배열을 복사해서 옮기는 방식으로 했다.

동작

		arr = new int[N][M];
		temp = new int[N][M];

먼저 회전 시킬 배열을 arr로 만들어주고, 회전 시킬 배열에 값을 옮겨줄 temp배열도 생성해준다.
arr의 이동한 좌표에 temp의 값을 넣어주는 방식이다.


		// M의 절반값 까지회전.
		int loop = Math.min(N, M) / 2;
		int node[][] = new int[loop][4];

		// 내부회전 좌표 생성
		for(int i=0; i<loop; i++) {
			node[i][0] = i; // x1 
			node[i][1]= i; // y1
			node[i][2] = (N-1)-i; // x2 
			node[i][3] = (M-1)-i; // y2
		}	

		// 전체 회전 반복
		while(R-->0) {
            copy();
			// 내부 회전 반복
			for(int i=0; i<loop; i++) {
				rotation(node[i][0], node[i][1], node[i][2], node[i][3]);
			}	
		}

문제의 제한 부분에 보면, MN중에 작은값의 나머지가 2이라고 적혀있기때문에
내부 반복을 위해서는 MN중에 작은 값을 선택해서 2로 나누어서 범위를 지정해주면 된다.

만약 N=4 M=4일 때, 4x4의 배열이 되는데, 바깥 배열의 범위는 (0,0) ~ (3,3)이 되고
안쪽 배열은 (1,1) ~ (2,2)가 된다.

배열 회전을 시작하는 (0,0)과 (1,1)의 범위를 지정해주기위해서 필요하다. 회전하는 내부 배열이 2개임을 의미한다.






코드


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

public class Main {
	static int arr[][];
	static int temp[][];
	static int N, M;

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

		st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		int R = Integer.parseInt(st.nextToken());

		arr = new int[N][M];
		temp = new int[N][M];
		for(int i=0; i<N; i++) {
			st = new StringTokenizer(br.readLine());

			for(int j=0; j<M; j++) {
				arr[i][j] = Integer.parseInt(st.nextToken());
			}
		}

		// M의 절반값 까지회전.
		int loop = Math.min(N, M) / 2;
		int node[][] = new int[loop][4];

		// 내부회전 좌표 생성
		for(int i=0; i<loop; i++) {
			node[i][0] = i; // x1 
			node[i][1]= i; // y1
			node[i][2] = (N-1)-i; // x2 
			node[i][3] = (M-1)-i; // y2
		}	

		// 전체 회전 반복
		while(R-->0) {
            copy();
			// 내부 회전 반복
			for(int i=0; i<loop; i++) {
				rotation(node[i][0], node[i][1], node[i][2], node[i][3]);
			}	
		}

		for(int i=0; i<N; i++) {
			for(int j=0; j<M; j++) {
				sb.append(arr[i][j] + " ");
			}
			sb.append('\n');
		}

		System.out.println(sb);

	} // End of main

	static void copy() {
		for(int i=0; i<N; i++) {
			for(int j=0; j<M; j++) {
				temp[i][j] = arr[i][j];
			}
		}
	}

	static void rotation(int x1, int y1, int x2, int y2) {
		// 반시계 방향 회전

		// 상단 회전
		// temp(0, 3) -> arr(0, 2)
		// temp(0, 2) -> arr(0, 1)
		// temp(0, 1) -> arr(0, 0)
		for(int i=y2; i>y1; i--) {
			arr[x1][i-1] = temp[x1][i];
		}

		// 좌측 회전
		// temp(0,0) -> arr(1, 0)
		// temp(1,0) -> arr(2,0)
		// temp(2,0) -> arr(3,0)
		// temp(3,0) -> arr(4,0)
		for(int i=x1; i<x2; i++) {
			arr[i+1][y1] = temp[i][y1];
		}

		// 하단 회전
		// temp(4,0) -> arr(4,1)
		// temp(4,1) -> arr(4,2)
		// temp(4,2) -> arr(4,3)
		for(int i=y1; i<y2; i++) {
			arr[x2][i+1] = temp[x2][i];
		}

		// 우측 회전
		// temp(4,3) -> arr(3,3)
		// temp(3,3) -> arr(2,3)
		// temp(2,3) -> arr(1,3)
		// temp(1,3) -> arr(0,3)
		for(int i=x2; i>x1; i--) {
			arr[i-1][y2] = temp[i][y2];
		}

	} // End of rotation
} // End of Main class

0개의 댓글