백준 17406 - 배열 돌리기 4

Java

17406 번 - 배열 돌리기 4

문제

크기가 N×M 크기인 배열 A가 있을때, 배열 A의 값은 각 행에 있는 모든 수의 합 중 최솟값을 의미한다.
배열 A와 사용 가능한 회전 연산이 주어졌을 때, 배열 A의 값의 최솟값을 구해보자. 회전 연산은 모두 한 번씩 사용해야 하며, 순서는 임의로 정해도 된다.

접근 방법

배열 돌리기 1,2,3을 해결하였으면 쉽게 풀 수 있는 문제였다.
주어진 문제는 k개의 회전 연산을 섞어가며 수행한 뒤, 변환 된 배열의 최소 값을 구하는 것이다.
위 문제를 해결하기 위해 코드의 구성은 다음과 같다.

1. k개의 회전 연산을 순열을 통해 섞는다.
2. 섞은 회전 연산 k개를 수행하여 배열을 변환한다.
3. 변환한 배열 n개의 행들의 값 합을 구하여, 그 중 최솟값을 구한다.

코드

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

public class Main {
	static int n, m, k, result = 987654321, r, c, s, size;
	static int[] sel, vsi;
	static int[][] arr, oper, saved, nArr;
    public static void main(String []args) throws IOException {        
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer stk = new StringTokenizer(br.readLine());
    	n = stoi(stk.nextToken());
    	m = stoi(stk.nextToken());
    	k = stoi(stk.nextToken());
    	arr = new int[n][m];	// 값 배열
    	saved = new int[n][m];	// 백업 내용
    	oper = new int[k][3];	// 연산

		// A 배열과, 백업 용 배열을 초기화 한다.
    	for(int i = 0; i < n; i++) {
    		stk = new StringTokenizer(br.readLine());
    		for(int j = 0; j < m; j++) {
    			arr[i][j] = stoi(stk.nextToken());
    			saved[i][j] = arr[i][j];
    		}
    	}
    	// 회전 연산의 정보를 저장한다.
    	for(int i = 0; i < k; i++) {
    		stk = new StringTokenizer(br.readLine());
    		for(int j = 0; j < 3; j++) {
    			oper[i][j] = stoi(stk.nextToken());
    		}
    	}
    	
		// 회전 연산 순서에 대한 순열을 제작할 대 필요한 배열 선언
    	sel = new int[k];
    	vsi = new int[k];
    	
		// 순열을 제작하고, 그에 따른 회전 연산을 수행한다.
    	DFS(0);
    	
    	System.out.println(result);
    	br.close();
    }
    // K! 만큼 반복을 하여 회전 연산 순서 순열을 만든다.
    static void DFS(int lv) {
    	if(lv == k) {
			// A 배열을 초기 상태로 복구한다.
    		for(int i = 0; i < n; i++) {
    			arr[i] = saved[i].clone();
    		}
    		Cal();	// 회전 연산
    		int sum = 0;
			// 회전 연산 후 배열의 값 구하기
    		for(int[] vv : arr) {
    			sum = 0;
    			for(int v : vv) {
    				sum += v;
    			}
				// 최솟 값 저장한다.
    			result = Math.min(sum, result);
    		}
    		return;
    	}
    	for(int i = 0; i < k; i++) {
    		if(vsi[i] == 0) {
    			vsi[i] = 1;
    			sel[lv] = i;
    			DFS(lv + 1);
    			vsi[i] = 0;
    		}
    	}
    }
    
    static int i, j, d = 0;
	static int dy[] = {1,0,-1,0};		// 하, 우, 상, 좌
	static int dx[] = {0,1,0,-1};
	
    static void Cal() {
    	for(int lv = 0; lv < k; lv++) {
    		r = oper[sel[lv]][0];
    		c = oper[sel[lv]][1];
    		s = oper[sel[lv]][2];
    		size = 2*s+1;
    		nArr = new int[size][size];
    		// 돌릴 2차원 배열 크기 만큼 arr에서 떼어온다.
    		for(int i = 0; i < size; i++) {
    			for(int j = 0; j < size; j++) {
    				nArr[i][j] = arr[r - s - 1 + i][c - s - 1 + j]; 
        		}
    		}
    		// 떼어온 2차원 배열을 시계방향으로 한칸 이동한다
    		for(int idx = 0; idx < s; idx++) {
				i = idx;
				j = idx;
				d = 0;
				int tmp = nArr[i][j];
				
				while(d != 4) {	
					// 만약 범위를 벗어나면, 대입하는 값의 방향을 바꾼다.
					if(i + dy[d] < idx || i + dy[d] >= size - idx  || j + dx[d] < idx || j + dx[d] >= size - idx) {		
						d++;		
						continue;
					}
					nArr[i][j] = nArr[i + dy[d]][j + dx[d]];
					i += dy[d];
					j += dx[d];
				}
				nArr[idx][idx + 1] = tmp;
			}
    		// 떼어온 2차원 배열을 다시 원본에 붙힌다.
    		for(int i = 0; i < size; i++) {
    			for(int j = 0; j < size; j++) {
    				arr[r - s - 1 + i][c - s - 1 + j] = nArr[i][j]; 
        		}
    		}
    	}
    }
    
    static int stoi(String str) {
    	return Integer.parseInt(str);
    }
}

총평

난이도

⭐⭐★★★

후기

문제 조건인 행/열 최소 값은 2의 배수이다를 읽지 않아, 쓸데없이 고생했다.
문제를 잘 읽어라는 교수님 말씀이 뭔지 새삼 깨닫게된다 정말로,,

개선할 점

문제 좀 읽자!!!!