백준 17406번 - 배열 돌리기 4

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

17406번: 배열 돌리기 4

 

 

 

 

 

하... 배열 돌리기의 끝판왕이다. 순열 + 배열 돌리기가 합쳐진 문제이다.

 

연산을 저장하기 위한 클래스를 만들었다. 그리고 연산이 들어올때마다 객체를 생성해 배열에 저장해준다.

그리고 순열을 돌린다. 순열을 저장하기 위한 결과 배열을 만들어줬다.

 

순열이 완성이 되면, 배열을 돌려준다.

 

배열을 돌리는데 방향별로 for문을 돌려서 옮겨주었다. 먼저 하던 것은 반시계였는데, 이번 것은 시계라서 처음에 잘못 풀었다.. 인덱스에 유의해야 한다.

 

중간에 틀렸는데 순열이 하나 완성될 때마다 리턴하기 전에 원래 배열로 돌려놓아야 한다.

초기화!!!!!!!

안돌려 놓으면 연산이 수행된 것에 이어서 수행이 된다.

 

 

 

 

 

코드

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

public class Main {
	static int N, M, K;
	static int[][] A;
	static int[][] A_copy;
	static boolean[] visited;
	static Operation[] ops;
	static Operation[] result;
	static int min = Integer.MAX_VALUE;
	
	static class Operation {
		int r;
		int c;
		int s;
		
		public Operation(int r, int c, int s) {
			this.r = r;
			this.c = c;
			this.s = s;
		}
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		K = Integer.parseInt(st.nextToken());
		
		A = new int[N + 1][M + 1];
		A_copy = new int[N + 1][M + 1];

		for(int i = 1; i <= N; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			
			for(int j = 1; j <= M; j++) {
				A[i][j] = A_copy[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		
		ops = new Operation[K];
		for(int i = 0; i < K; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			
			int r = Integer.parseInt(st.nextToken());
			int c = Integer.parseInt(st.nextToken());
			int s = Integer.parseInt(st.nextToken());
			
			ops[i] = new Operation(r, c, s);
		}
		
		//연산에 대해 순열
		visited = new boolean[K];
		result = new Operation[K];
		
		permutation(0);
		
		//출력
		System.out.println(min);
	}

	public static void permutation(int count) {
		if(count == K) {
			for(int i = 0; i < K; i++) {
				rotate(result[i].r, result[i].c, result[i].s);
			}
			
			int a = Integer.MAX_VALUE;
			for(int i = 1; i <= N; i++) { //배열 A의 값 구하기
				int sum = 0;
				for(int j = 1; j <= M; j++) {
					sum += A[i][j];
				}
				a = Math.min(a, sum);
			}
			
			min = Math.min(min, a); //A값의 최솟값 갱신
			
			//배열 A 원본으로 되돌려놓기
			for(int i = 1; i <= N; i++) {
				for(int j = 1; j <= M; j++) {
					A[i][j] = A_copy[i][j];
				}
			}
			
			return;
		}
		
		for(int i = 0; i < K; i++) {
			if(visited[i]) continue;
			
			visited[i] = true;
			result[count] = ops[i];
			permutation(count + 1);
			visited[i] = false;
		}
	}

	public static void rotate(int r, int c, int s) {
		int depth = (s * 2 + 1) / 2;
		
		for(int d = 0; d < depth; d++) {
			int tmp = A[r - s + d][c - s + d];
			
			for(int i = r - s + d; i < (r + s - d); i++) { // ↑
				A[i][c - s + d] = A[i + 1][c - s + d];
			}
			
			for(int i = c - s + d; i < (c + s - d); i++) { // ←
				A[r + s - d][i] = A[r + s - d][i + 1];
			}

			for(int i = (r + s - d); i >= (r - s + d + 1); i--) { // ↓
				A[i][c + s - d] = A[i - 1][c + s - d];
			}

			for(int i = (c + s - d); i >= (c - s + d + 1); i--) { // →
				A[r - s + d][i] = A[r - s + d][i - 1]; 
			}
			
			A[r - s + d][c - s + d + 1] = tmp;
		}
	}

}

 

 

 

 

 

결과