[BOJ] Q17406 배열 돌리기4

🔗문제 링크

BOJ 17406번

🔒 문제 설명

배열을 회전연산을 수행할 수 있다.

회전연산 (r,c,s)는 (r-s,c-s) ~ (r+s,c+s) 범위로 이루어진 정사각형을 시계 방향으로 한칸씩 돌린다는 의미이다.

회전연산이 두 개 이상이면 연산 순서에 따라 최정 배열이 달라진다.

배열의 값은 각 행의 합계중 최소값을 의미한다.

이 때, 가능한 회전연산이 주어졌을 때, 회전연산을 모두 사용하여 배열의 최솟값을 구하자.

🧾 입력 예시

5 6 2
1 2 3 2 5 6
3 8 7 2 1 3
8 2 3 1 4 5
3 4 5 1 1 1
9 3 2 1 4 3
3 4 2
4 2 1

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

두번째 줄부터 N개의 줄에는 배열이 주어진다.

다음 K개의 줄에는 회전연산의 정보가 주어진다.

1은 장애물이 있는 곳으로, 파이프 이동에 방해를 준다.

🔎 출력 예시

12

🔑 문제 풀이

1. 배열 base, 회전연산을 담을 배열 rotate을 생성한다.

2. DFS를 통하여 회전연산을 할 순서를 rotateList에 담는다.

3. rotateList 순서에 따라 회전연산을 수행(rotate())한다.

4. 회전연산의 결과값으로 ret를 갱신한다.

💻 전체 코드

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

public class Q17406_RotateArr {
	public static void main(String[] args) throws IOException {
		Q17406_RotateArr z = new Q17406_RotateArr();
		z.solution();
	}
	int N = 0;
	int M = 0;
	int K = 0;
	int ret = 0;
	int[][] base;
	int[][] rotate;
	private void solution() throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		ret = Integer.MAX_VALUE;
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		K = Integer.parseInt(st.nextToken());
		base = new int[N+1][M+1];
		rotate = new int[K][3];
		for(int i=1 ; i<=N ; i++) {
			st = new StringTokenizer(br.readLine());
			for(int j=1 ; j<=M ; j++) {
				base[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		for(int i=0 ; i<K ; i++) {
			st = new StringTokenizer(br.readLine());
			for(int j=0 ; j<3 ; j++) {
				rotate[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		List<int[]> rotateList = new ArrayList<>();
		boolean[] visited = new boolean[K];
		dfs(rotateList, 0, visited);
		System.out.println(ret);

	}
	private void dfs(List<int[]> rotateList, int dep, boolean[] visited) {
		if(dep==K) {
			int[][] copyArr = copyArr();
			int min = rotate(copyArr,rotateList);
			ret = Math.min(ret, min);
//			System.out.println(min);
//			printMap(copyArr);
			return;
		}
		for(int i=0 ; i<K ; i++) {
			if(!visited[i]) {
				visited[i] = true;
				rotateList.add(new int[] {rotate[i][0],rotate[i][1],rotate[i][2]});
				dfs(rotateList,dep+1,visited);
				rotateList.remove(rotateList.size()-1);
				visited[i] = false;
			}
		}
	}
	private int[][] copyArr(){
		int[][] ret = new int[N+1][M+1];
		for(int i=1 ; i<N+1 ; i++) {
			for(int j=1 ; j<M+1 ; j++) {
				ret[i][j] = base[i][j];
			}
		}
		return ret;
	}
	
	private int rotate(int[][] arr,List<int[]> rotateList) {
		for(int i=0 ; i<K ; i++) {
			int row = rotateList.get(i)[0];
			int col = rotateList.get(i)[1];
			int len = rotateList.get(i)[2];
			for(int rot=len ; rot>0 ; rot--) {
				rotateArr(arr,row-rot,col-rot,rot);
			}
		}
		return findMin(arr);
	}
	
	private void rotateArr(int[][] arr,int row, int col, int len) {
		// 오른쪽으로
		int temp1 = arr[row][col];
		int temp2 = 0;
		for(int j=col+1 ; j<=col+2*len ; j++) {
			temp2 = arr[row][j];
			arr[row][j] = temp1;
			temp1 = temp2;
		}
		// 아래쪽으로
		for(int i=row+1 ; i<=row+2*len ; i++) {
			temp2 = arr[i][col+2*len];
			arr[i][col+2*len] = temp1;
			temp1 = temp2;
		}
		// 왼쪽으로
		for(int j=col+2*len-1 ; j>=col ; j--) {
			temp2 = arr[row+2*len][j];
			arr[row+2*len][j] = temp1;
			temp1 = temp2;
		}
		// 위쪽으로
		for(int i=row+2*len-1 ; i>=row ; i--) {
			temp2 = arr[i][col];
			arr[i][col] = temp1;
			temp1 = temp2;
		}
	}
	
	private int findMin(int[][] arr) {
		int ret = Integer.MAX_VALUE;
		for(int x=1 ; x<arr.length ; x++) {
			int[] temp = arr[x];
			int sum = 0;
			for(int i=0 ; i<temp.length ; i++) {
				sum += temp[i];
			}
			ret = Math.min(ret, sum);
		}
		return ret;
	}
	
	private void printMap(int[][] arr) {
		for(int i=1 ; i<=N ; i++) {
			for(int j=1 ; j<=M ; j++) {
				System.out.print(arr[i][j]+" ");
			}
			System.out.println();
		}
	}
}

📇 결과