[백준] 17406번: 배열 돌리기4 문제 풀이

작성 전 회고

이번 문제는 입력받은 회전에 대한 정보들 내에서, 어떠한 순서로 회전해도 상관이 없었다.
처음에 문제를 풀 때, 입력받은 순서대로 회전을 하는 줄 알고, 주어진 테스트케이스만 믿고 문제를 제출했다가 틀렸었다. 다시 보니 순열 문제였다. 문제를 더 자세히 읽었어야 했다...

자료 구조 선언

원본 배열의 값을 담을 arr과, 회전한 상태의 새로운 배열을 담을 newArr, 회전에 대한 정보들을 담을 cycles 를 먼저 선언해주었다.

또한 이번 문제는 어떠한 순서로 회전해도 상관이 없는 조건이 붙어있기 때문에 순열을 구하는 문제였으므로, 순열을 담을 배열과 방문처리를 할 배열을 선언했다.

static int N, M, K;
static int [][]arr, newArr, cycles;
static int perm[];
static boolean v[];
static int ans = Integer.MAX_VALUE; // 최소 값을 구하기 위한 변수

---

배열 회전시키기

배열을 회전시키기 전에 임시 배열을 만들어주고 회전될 위치에 넣을 값을 임시 배열에 넣어준다.
주어진 배열의 범위만큼 4개의 반복문을 사용하여 시계방향으로 회전을 시켜준다.
한바퀴 회전이 끝나면 범위를 1씩 축소시키고 다시 회전을 진행한다.
회전이 끝났으면 회전이 된 숫자(0이 아닌 숫자)들만 newArr에 복사해준다.

static void cycleArr(int r, int c, int s) {
	int y1 = r-s;
	int x1 = c-s;
	int y2 = r+s;
	int x2 = c+s;
	int [][] tmp = new int [N+1][M+1]; // 회전시킨 값을 담을 임시 배열
	
	while (s-- > 0) {
    	// 오른쪽 회전
		for (int i = x1; i < x2; i++) tmp[y1][i+1] = newArr[y1][i];
		// 아래 회전
        for (int i = y1; i < y2; i++) tmp[i+1][x2] = newArr[i][x2];
		// 왼쪽 회전
        for (int i = x2; i > x1; i--) tmp[y2][i-1] = newArr[y2][i];
		// 위 회전
        for (int i = y2; i > y1; i--) tmp[i-1][x1] = newArr[i][x1];
		// 회전할 범위 1씩 축소
        x1 += 1;
		x2 -= 1;
		y1 += 1;
		y2 -= 1;
	}
	
	for (int i = 1; i <= N; i++) // 회전된 값이 담긴 임시 배열 newArr에 복사
		for (int j = 1; j <= M; j++) 
			if (tmp[i][j] != 0) newArr[i][j] = tmp[i][j]; // 회전된 값만 복사
}

---

순열 구하기

다양한 순서로 회전을 진행하기 위해 순열을 구한다.
하나의 순열이 완성이 되었다면, 주어진 순서대로 배열을 회전시켜 최솟값을 구하고 갱신한다.
이 때, 다양한 순서로 회전시켜보고 각각 최솟값을 비교해야하기 때문에, 원본 배열을 하나 복제해서 복제한 배열로 회전을 진행한다.
회전이 끝나면 최솟값을 갱신한다.

static void perm(int cnt) {
	if (cnt == K) {
		for (int i = 0; i <= N; i++) // 원본 배열 복제
			newArr[i] = Arrays.copyOf(arr[i], M+1);
		
		for (int i = 0; i < K; i++) { // 회전을 진행할 값을 꺼내어 회전 진행
			int r = cycles[perm[i]][0];
			int c = cycles[perm[i]][1];
			int s = cycles[perm[i]][2];
			cycleArr(r, c, s);
		}
		
		int sum = getMinSum(); // 회전된 배열의 최솟값 구하기
		ans = sum < ans ? sum : ans; 
	}
	
	for (int i = 0; i < K; i++) {
		if (v[i]) continue;
		perm[cnt] = i;
		v[i] = true;
		perm(cnt + 1);
		v[i] = false;
	}
}

---

전체 코드

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

public class Main {
	static int N, M, K;
	static int [][]arr, newArr, cycles;
	static int perm[];
	static boolean v[];
	static int ans = Integer.MAX_VALUE;
	
	static int getMinSum() {
		int b = Integer.MAX_VALUE;
		for (int i = 1; i <= N; i++) {
			int a = 0;
			for (int j = 1; j <= M; j++) 
				a += newArr[i][j];
			b = b > a ? a : b;
		}
		return b;
	}
	
	static void cycleArr(int r, int c, int s) {
		int y1 = r-s;
		int x1 = c-s;
		int y2 = r+s;
		int x2 = c+s;
		int [][] tmp = new int [N+1][M+1];
		
		while (s--> 0) {
			for (int i = x1; i < x2; i++) tmp[y1][i+1] = newArr[y1][i];
			for (int i = y1; i < y2; i++) tmp[i+1][x2] = newArr[i][x2];
			for (int i = x2; i > x1; i--) tmp[y2][i-1] = newArr[y2][i];
			for (int i = y2; i > y1; i--) tmp[i-1][x1] = newArr[i][x1];
			x1 += 1;
			x2 -= 1;
			y1 += 1;
			y2 -= 1;
		}
		
		for (int i = 1; i <= N; i++)
			for (int j = 1; j <= M; j++) 
				if (tmp[i][j] != 0) newArr[i][j] = tmp[i][j];
	}
	
	static void perm(int cnt) {
		if (cnt == K) {
			for (int i = 0; i <= N; i++) 
				newArr[i] = Arrays.copyOf(arr[i], M+1);
			
			for (int i = 0; i < K; i++) {
				int r = cycles[perm[i]][0];
				int c = cycles[perm[i]][1];
				int s = cycles[perm[i]][2];
				cycleArr(r, c, s);
			}
			
			int sum = getMinSum();
			ans = sum < ans ? sum : ans;
		}
		
		for (int i = 0; i < K; i++) {
			if (v[i]) continue;
			perm[cnt] = i;
			v[i] = true;
			perm(cnt + 1);
			v[i] = false;
		}
	}
	
	public static void main(String[] args) throws Exception {
		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];
		newArr = new int [N+1][];
		cycles = new int [K][];
		perm = new int [K];
		v = new boolean[K];
		
		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 t = 0; t < K; t++) {
			st = new StringTokenizer(br.readLine(), " ");
			int r = Integer.parseInt(st.nextToken());
			int c = Integer.parseInt(st.nextToken());
			int s = Integer.parseInt(st.nextToken());
			cycles[t] = new int [] {r, c, s};
		}
		
		perm(0);
		System.out.println(ans);
	}
}