[백준 17406] 배열 돌리기 4

[문제 바로가기]👇

17406번: 배열 돌리기 4

 

 

💡풀이💡

문제에서 알 수 있는 정보!

1.회전 연산 순서에 따라 배열 A의 값이 달라짐
2. 회전 연산은 모두 한 번씩 사용해야 함
>> nPn 순열!

회전 연산 nPn 순열을 만들어서 각 순열마다 배열 돌리기를 실행

배열 돌렸을 때 배열의 합 중 최솟값 찾기!

:: 배열의 합 : 각 행에 있는 모든 수의 합 중 최솟값

 

1. 입력 받기

기존 배열 정보과 회전 연산 정보를 저장한다.

이때 회전 연산을 순열로 만들어야 하기 때문에 만들어진 순열을 저장할 배열을 생성 

	static int N, M, K;
	static int[][] arr; // 기존 배열
	static int min;
	static int[] rotateArr; // 완성된 회전 연산 순열 저장
	static boolean[] v; // 순열에 저장할 때 사용했는지 확인
	static List<int[]> rotateInfo; // 회전 연산 정보 저장
	
	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());
		arr = new int[N+1][M+1];
		rotateArr = new int[K];
		v = new boolean[K];
		rotateInfo = new ArrayList<>();
		min = Integer.MAX_VALUE;
		
		for(int i=1; i<=N; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			for(int j=1; j<=M; j++) {
				arr[i][j] = Integer.parseInt(st.nextToken());
			}
		}
        
        	// 회전연산 정보 저장
        	for(int i=0; i<K; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			rotateInfo.add(new int[] {
				Integer.parseInt(st.nextToken()), 
				Integer.parseInt(st.nextToken()), 
				Integer.parseInt(st.nextToken())}
			);
		}
	}

 

2. 회전 연산 순열 생성

회전 연산 정보를 저장한 List에 입력 받은 순서대로 저장되어 있기 때문에

i를 저장해 List의 i번째 인덱스 값을 순열로 선택

 

📌놓쳤던 부분!

순열이 완성 될 때마다 회전 연산을 수행해야 하기 때문에 기존 배열의 값을 바꾸면 X!

기존 배열을 복사해서 사용해야 하는데 처음에는 기존 배열을 그대로 회전 연산을 시켜서 잘못된 답이 나왔었다.

 

전체 흐름

1) 기존 배열 복사하기

2) 완성된 순열 순서대로 회전 연산 수행하기

3) 모든 회전 연산이 끝나면 배열의 값 찾기

static void perm(int cnt) {
	if(cnt == K) { // 순열 완성
    
    		// 1) 기존 배열 복사하기
		int[][] input = new int[N+1][M+1];
		for(int i=1; i<=N; i++) {
			for(int j=1; j<=M; j++) input[i][j] = arr[i][j];
		}
        
        	// 2) 순열 순서대로 회전 연산 실행 
		for(int i=0; i<K; i++) {
			int r = rotateInfo.get(rotateArr[i])[0];
			int c = rotateInfo.get(rotateArr[i])[1];
			int s = rotateInfo.get(rotateArr[i])[2];
				
			rotate(r,c,s, input);
		}
        
        	// 3) 회전 연산 후 배열의 값 찾기
		for(int i=1; i<=N; i++) {
			int sum = 0;
			for(int j=1; j<=M; j++) sum += input[i][j];
			min = Math.min(min, sum);
		}
		return;
	}
        
	for(int i=0; i<K; i++) {
		if(v[i]) continue;
		v[i] = true;
		rotateArr[cnt] = i;
		perm(cnt+1);
		v[i] = false;
	}
}

 

3. 회전 연산 하기

회전 연산은 왼쪽 윗 칸이  (r-s, c-s), 오른쪽 아랫 칸이 (r+s, c+s)인 정사각형을 시계 방향 회전하는 것

>> 두 점으로 정사각형의 위,아래,왼쪽, 오른쪽 경계값을 알 수 있음

 

가장 바깥 열부터 안쪽으로

왼쪽 윗 칸 :  한 칸 아래(⬇), 한 칸 오른쪽(➡)으로 이동하고
오른쪽 아랫 칸 : 한 칸 위로(⬆), 한 칸 왼쪽(⬅)으로 이동

하기 때문에 정사각형의 위 경계값이 아래 경계값 보다 커지면 더 이상 안쪽에 남은 배열이 없음 >> 회전 종료! 

 

회전 한 번마다 각 경계값을 이동시켜 바깥에서 안쪽으로 들어가면서 회전시키기!

static void rotate(int r, int c, int s, int[][] input) {
	// 첫 시작 경계값
	int T = r-s;
	int R = c+s;
	int B = r+s;
	int L = c-s;
		
	// 배열 돌리기
	while(true) {
		if(T>=B) break;
			
		int temp = input[T][L];
		for(int i=T; i<B; i++) input[i][L] = input[i+1][L]; // ⬆
		for(int j=L; j<R; j++) input[B][j] = input[B][j+1]; // ⬅
		for(int i=B; i>T; i--) input[i][R] = input[i-1][R]; // ⬇
		for(int j=R; j>L; j--) input[T][j] = input[T][j-1];  // ➡
		input[T][L+1] = temp;
            
         	// 경계값 이동
        	T+=1; // 한 칸 아래로
		L+=1; // 한 칸 오른쪽으로
		B-=1; // 한 칸 위로
		R-=1; // 한 칸 왼쪽으로
	}
}

 

 

 

4. 전체 코드

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

public class Main {
	static int N, M, K;
	static int[][] arr;
	static int min;
	static int[] rotateArr;
	static boolean[] v;
	static List<int[]> rotateInfo;
	
	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());
		arr = new int[N+1][M+1];
		rotateArr = new int[K];
		v = new boolean[K];
		rotateInfo = new ArrayList<>();
		min = Integer.MAX_VALUE;;
		
		for(int i=1; i<=N; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			for(int j=1; j<=M; j++) {
				arr[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		
		for(int i=0; i<K; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			rotateInfo.add(new int[] {
					Integer.parseInt(st.nextToken()), 
					Integer.parseInt(st.nextToken()), 
					Integer.parseInt(st.nextToken())}
			);
		}
		perm(0);
		System.out.println(min);
	}
	
	static void perm(int cnt) {
		if(cnt == K) {
			int[][] input = new int[N+1][M+1];
			for(int i=1; i<=N; i++) {
				for(int j=1; j<=M; j++) input[i][j] = arr[i][j];
			}
			for(int i=0; i<K; i++) {
				int r = rotateInfo.get(rotateArr[i])[0];
				int c = rotateInfo.get(rotateArr[i])[1];
				int s = rotateInfo.get(rotateArr[i])[2];
				
				rotate(r,c,s, input);
			}
			for(int i=1; i<=N; i++) {
				int sum = 0;
				for(int j=1; j<=M; j++) sum += input[i][j];
				min = Math.min(min, sum);
			}
			return;
		}
        
		for(int i=0; i<K; i++) {
			if(v[i]) continue;
			v[i] = true;
			rotateArr[cnt] = i;
			perm(cnt+1);
			v[i] = false;
		}
	}
	
	static void rotate(int r, int c, int s, int[][] input) {
		int T = r-s;
		int R = c+s;
		int B = r+s;
		int L = c-s;
		
		// 배열 돌리기
		while(true) {
			if(T>=B) break;
			
			int temp = input[T][L];
			for(int i=T; i<B; i++) input[i][L] = input[i+1][L]; // ^
			for(int j=L; j<R; j++) input[B][j] = input[B][j+1]; // <
			for(int i=B; i>T; i--) input[i][R] = input[i-1][R]; // v
			for(int j=R; j>L; j--) input[T][j] = input[T][j-1];  // >
			input[T][L+1] = temp;
            
            T+=1;
			L+=1;
			B-=1;
			R-=1;
		}
	}
}