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

www.acmicpc.net/problem/17406

17406번: 배열 돌리기 4

풀이

 

시계방향 회전의 원리만 알면, 이후에는 순열로써 문제를 풀면 된다.

 

N*M 행렬이라고 할 때, min(N,M) / 2가 회전해야할 둘레의 개수라고 볼 수 있다. (위의 그림 참고)

그리고 처음 회전의 시작점을 (0,0)이라고 하고, 회전횟수가 i 번째라고 할 때, 이 i번째 둘레를 회전할 때의 시작점은 (i,i) 다.

이를 이용해서 둘레 회전을 시켜주면 된다!

 

방향이 너무 헷갈렸었는데 이것만 주의해주면 풀 수 있다.

시계방향으로 회전한다고 할 때 원소가 이동해야 할 방향은 반시계방향이므로 dx, dy 배열을 설정할 때 그 순서로 해주면 된다.

public class BOJ_17406 {
	static int N, M, R;
	static int[][] matrix;
	static int[][] arr;
	static List<int[]> list = new ArrayList<>();	// (r,c,s) 담기
	static int min;	// 최종 정답
	
	public static void main(String[] args) throws IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(in.readLine(), " ");
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		R = Integer.parseInt(st.nextToken());	// 회전 횟수

		matrix = new int[N][M];
		arr = new int[N][M];	// matrix의 복사본
		
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(in.readLine(), " ");
			for (int j = 0; j < M; j++) {
				matrix[i][j] = Integer.parseInt(st.nextToken());
				arr[i][j] = matrix[i][j];
			}
		}
		
		for (int i = 0; i < R; i++) {
			st = new StringTokenizer(in.readLine(), " ");
			int r = Integer.parseInt(st.nextToken())-1;	// 0 base index
			int c = Integer.parseInt(st.nextToken())-1;	// 0 base index
			int s = Integer.parseInt(st.nextToken());

			list.add(new int[] { r, c, s });	// list에 저장
		}
		
		min = Integer.MAX_VALUE;
		perm(0,new int[R], new boolean[R]);	// 명령 순ㅅ => 순열
		System.out.println(min);
	}
	
	// arr 배열을 다시 초기 상태로 만들기
	static void init() {
		for(int i=0;i<N;i++) {
			for(int j=0;j<M;j++) {
				arr[i][j] = matrix[i][j];
			}
		}
	}
	
	// 순열
	static void perm(int toSelect, int[] selected, boolean[] visited) {
		if(toSelect==R) {
			init();
			for(int i=0;i<R;i++) {
				int idx = selected[i];
				rotate(list.get(idx));	// 만들어진 명령 순서에 따라 회전하기
			}
			// 행렬의 각 행의 합 구해서 최소 합 구하기
			for(int i=0;i<N;i++) {
				int sum = 0;
				for(int j=0;j<M;j++) {
					sum += arr[i][j];
				}
				min = Math.min(min, sum);
			}
			return;
		}
		
		for(int i=0;i<R;i++) {
			if(!visited[i]) {
				visited[i] = true;
				selected[toSelect] = i;
				perm(toSelect+1, selected,visited);
				visited[i] = false;
			}
		}
	}
	// 시계방향 회전
	static void rotate(int[] info) {
		int r = info[0];
		int c = info[1];
		int s = info[2];

		int sx = r - s, sy = c - s;
		int ex = r + s, ey = c + s;

		int group = s;
		int[] dx = { 1, 0, -1, 0 };
		int[] dy = { 0, 1, 0, -1 };
		for (int i = 0; i < group; i++) {
			int x = sx + i;
			int y = sy + i;
			int d = 0;
			int tmp = arr[x][y];
			while (d < 4) {
				int nx = x + dx[d];
				int ny = y + dy[d];
				if (nx >= sx + i && nx <= ex - i && ny >= sy + i && ny <= ey - i) {
					arr[x][y] = arr[nx][ny];
					x = nx;
					y = ny;
				} else {
					d++;
				}
			}
			arr[x][y + 1] = tmp;
		}

	}
}