[백준 17406 - Java] 배열 돌리기 4

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

17406번: 배열 돌리기 4

 

문제

크기가 N×M 크기인 배열 A가 있을때, 배열 A의 값은 각 행에 있는 모든 수의 합 중 최솟값을 의미한다. 배열 A가 아래와 같은 경우 1행의 합은 6, 2행의 합은 4, 3행의 합은 15이다. 따라서, 배열 A의 값은 4이다.

1 2 3
2 1 1
4 5 6

배열은 회전 연산을 수행할 수 있다. 회전 연산은 세 정수 (r, c, s)로 이루어져 있고, 가장 왼쪽 윗 칸이 (r-s, c-s), 가장 오른쪽 아랫 칸이 (r+s, c+s)인 정사각형을 시계 방향으로 한 칸씩 돌린다는 의미이다. 배열의 칸 (r, c)는 r행 c열을 의미한다.

예를 들어, 배열 A의 크기가 6×6이고, 회전 연산이 (3, 4, 2)인 경우에는 아래 그림과 같이 회전하게 된다.

A[1][1]   A[1][2] → A[1][3] → A[1][4] → A[1][5] → A[1][6]
             ↑                                       ↓
A[2][1]   A[2][2]   A[2][3] → A[2][4] → A[2][5]   A[2][6]
             ↑         ↑                   ↓         ↓
A[3][1]   A[3][2]   A[3][3]   A[3][4]   A[3][5]   A[3][6]
             ↑         ↑                   ↓         ↓
A[4][1]   A[4][2]   A[4][3] ← A[4][4] ← A[4][5]   A[4][6]
             ↑                                       ↓
A[5][1]   A[5][2] ← A[5][3] ← A[5][4] ← A[5][5] ← A[5][6]

A[6][1]   A[6][2]   A[6][3]   A[6][4]   A[6][5]   A[6][6]

회전 연산이 두 개 이상이면, 연산을 수행한 순서에 따라 최종 배열이 다르다.

다음은 배열 A의 크기가 5×6이고, 회전 연산이 (3, 4, 2), (4, 2, 1)인 경우의 예시이다.

배열 A에 (3, 4, 2), (4, 2, 1) 순서로 연산을 수행하면 배열 A의 값은 12, (4, 2, 1), (3, 4, 2) 순서로 연산을 수행하면 15 이다.

배열 A와 사용 가능한 회전 연산이 주어졌을 때, 배열 A의 값의 최솟값을 구해보자. 회전 연산은 모두 한 번씩 사용해야 하며, 순서는 임의로 정해도 된다.

입력

첫째 줄에 배열 A의 크기 N, M, 회전 연산의 개수 K가 주어진다.

둘째 줄부터 N개의 줄에 배열 A에 들어있는 수 A[i][j]가 주어지고, 다음 K개의 줄에 회전 연산의 정보 r, c, s가 주어진다.

출력

배열 A의 값의 최솟값을 출력한다.

제한

• 3 ≤ N, M ≤ 50
• 1 ≤ K ≤ 6
• 1 ≤ A[i][j] ≤ 100
• 1 ≤ s
• 1 ≤ r-s < r < r+s ≤ N
• 1 ≤ c-s < c < c+s ≤ M

 

풀이

 

K개의 회전을 어떤 순서로 진행하냐에 따라 배열이 달라지기 때문에 저는 재귀를 이용해서 회전 연산을 수행하는 모든 순서를 확인하는 방식으로 문제를 해결했습니다.

K개의 회전 순서를 배치한 후에 회전 연산을 수행하고 회전 결과 배열에서 배열의 값을 계산한 후에 최솟값을 갱신해 가는 방식으로 구현했습니다.

 

import java.util.Scanner;

public class Main {

	static int N, M, K;
	static int[][] map;
	static int[][] temp;
	static int[][] rotation;
	static int[] visited;
	static int[] order;
	static int answer = -1;
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		N = sc.nextInt();
		M = sc.nextInt();
		K = sc.nextInt();
		
		map = new int[N][M];
		rotation = new int[K][3];
		visited = new int[K];
		order = new int[K];
		
		for(int i=0; i<N; i++) {
			for(int j=0; j<M; j++) {
				map[i][j] = sc.nextInt();
			}
		}
		for(int i=0; i<K; i++) {
			rotation[i][0] = sc.nextInt()-1;
			rotation[i][1] = sc.nextInt()-1;
			rotation[i][2] = sc.nextInt();
		}
		
		dfs(0);
		
		System.out.println(answer);
	}
	
	// 회전 순서 추가하는 함수 
	static void dfs(int cnt) {
		// 순서 K개 추가 완료 
		if(cnt == K) {
			// 회전 수행 
			doRotate();
			return ;
		}
		
		for(int i=0; i<K; i++) {
			if(visited[i] == 1)
				continue;
			visited[i] = 1;
			order[cnt] = i;
			dfs(cnt+1);
			visited[i] = 0;
		}
	}

	static void doRotate() {
		temp = new int[N][M];
		// 배열 복사 
		for (int i = 0; i < N; i++) {
			System.arraycopy(map[i], 0, temp[i], 0, M);
		}
		
		for(int i=0; i<K; i++) {
			int move = order[i];

			// 사각형 하나씩 함수 호출해 회전 
			for (int j = 0; j < rotation[move][2]; j++) {
				
				int x1 = rotation[move][0] - rotation[move][2] + j;
				int y1 = rotation[move][1] - rotation[move][2] + j;
				
				int x2 = rotation[move][0] + rotation[move][2] - j;
				int y2 = rotation[move][1] + rotation[move][2] - j;

				rotate(x1, y1, x2, y2);
			}
		}
		
		calcMatrix();
	}
	
	//사각형 하나의 회전 수행하는 함수 
	static void rotate(int x1, int y1, int x2, int y2) {
		int tmp1, tmp2;

	    // 윗변 오른쪽 
	    tmp1 = temp[x1][y2];
	    for (int y = y2; y > y1; y--) {
	      temp[x1][y] = temp[x1][y - 1];
	    }

	    // 오른쪽변 아래 
	    tmp2 = tmp1;
	    tmp1 = temp[x2][y2];

	    for (int x = x2; x > x1; x--) {
	      if (x - 1 == x1) {
	        temp[x][y2] = tmp2;
	        continue;
	      }
	      temp[x][y2] = temp[x - 1][y2];
	    }

	    // 아랫변 왼쪽 
	    tmp2 = tmp1;
	    tmp1 = temp[x2][y1];

	    for (int y = y1; y < y2; y++) {
	      if (y + 1 == y2) {
	        temp[x2][y] = tmp2;
	        continue;
	      }

	      temp[x2][y] = temp[x2][y + 1];
	    }

	    // 왼쪽변 위 
	    tmp2 = tmp1;

	    for (int x = x1; x < x2; x++) {
	      if (x + 1 == x2) {
	        temp[x][y1] = tmp2;
	        continue;
	      }

	      temp[x][y1] = temp[x + 1][y1];
	    }
	}
	
	// 배열의 값 계산하는 함수 
	static void calcMatrix() {
		
		for(int i=0; i<N; i++) {
			int sum = 0;
			for(int j=0; j<M; j++) {
				sum+=temp[i][j];
			}
			if(answer == -1 || answer > sum)
				answer = sum;
		}
	}
}