문제

BOJ 17406: 배열 돌리기 4 https://www.acmicpc.net/problem/17406

풀이

• 입력받은 조건을 백트래킹을 통해 여러 순서로 조합하여 회전시켜야한다.
  • 입력 받은 조건을 console 배열에 차례로 넣는다.
  • 백트래킹을 사용하여 순서를 새롭게 조합한다.
  • nMap 배열을 복제한다.
  • console 배열에 사용할 idx로 result 배열에 있는 0 ~ K 까지의 수를 사용한다.
  • result 배열에 있는 수의 순서대로 rotate 메소드를 호출하여 nMap 배열을 회전시킨다.
  • 조건 끝(M 개의 조합)까지 회전이 끝난 nMap 배열에서 sumRow 메소드를 통해 열의 최솟값을 얻는다.
• 최솟값을 출력한다.

시계방향으로 회전 시킬 때 왼쪽의 수를 오른쪽으로 넣으면 추가적인 메모리가 필요하다.
따라서 반시계방향으로 수를 넣도록 구현하면 비교적 효율적으로 회전시킬 수 있다.

코드

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

public class Main {
	
	static int N, M, K;
	static int[][] graph; // 원래 배열
	static int[][] console; // 입력된 조건 넣을 배열
	static int min; // 구해야 할 답; 열 중 최솟값
	static boolean[] isVisited; // 백트래킹 중에 처리할 방문배열
	static int[] result; // 백트래킹 중 사용할 배열

	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		min = Integer.MAX_VALUE;
		
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		K = Integer.parseInt(st.nextToken()); // 조건 갯수
		
		console = new int[K][3]; // 순열로 조합 할 조건 배열
		isVisited = new boolean[K];
		result = new int[K];
		graph = new int[N][M];
		
        //원래 배열 입력
		for(int i=0; i<N; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			for(int j=0; j<M; j++) {
				graph[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		
		// 회전 중심 좌표, 반지름 입력	
		for(int i=0; i<K; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			int r = Integer.parseInt(st.nextToken()) - 1;
			int c = Integer.parseInt(st.nextToken()) - 1;
			int s = Integer.parseInt(st.nextToken());
			
			console[i] = new int[] {r, c, s}; // 입력 받은 조건을 순서대로 console 배열에 넣음
		}
		br.close();
		
		
		
		dfsConsole(0);
		
		System.out.println(min);
		
	}
	
	static void dfsConsole(int depth) {
		
		if(depth == K) {
			int[][] nMap = copyMap(); // 원 배열을 복사해서 사용
			
			for(int idx : result) { // 조합한 순서대로 
				int r = console[idx][0];
				int c = console[idx][1];
				int s = console[idx][2];
				
				rotate(r, c, s, nMap); // 회전시킴
			}
			
			min = Math.min(min, sumRow(nMap)); // 최솟값 찾기
			return;	
		}
		
		for(int i=0; i<K; i++) {
			if(!isVisited[i]) {
				isVisited[i] = true; // 자기 자신은 넣지 않기 위한 방문 처리
				
				result[depth] = i; // 깊이를 인덱스로 하여 0~K 까지의 수를 순열로 넣음
				dfsConsole(depth + 1);
				
				isVisited[i] = false;
			}
		}
	}
	//회전시키는 메소드
	static void rotate(int x, int y, int r, int[][] nMap) {		
		
		for(int i=1; i<=r; i++) { // 회전 범위를 1부터 입력값까지 올림
			Pos start = new Pos(x-i, y-i); // 왼쪽 윗 자리의 숫자를 start로 잡음
			
			int value = nMap[start.x][start.y];
			
			Pos temp = start;
			
			for(int j=1; j<= i*2; j++) { // 왼쪽 줄의 아래 숫자를 위로 옮김
				Pos next = new Pos(temp.x+1, temp.y);
				nMap[temp.x][temp.y] = nMap[next.x][next.y];
				temp = next;
			}
			for(int j=1; j<= i*2; j++) { // 아랫 줄의 오른쪽 숫자를 왼쪽으로 옮김
				Pos next = new Pos(temp.x, temp.y+1);
				nMap[temp.x][temp.y] = nMap[next.x][next.y];
				temp = next;
			}
			for(int j=1; j<= i*2; j++) { // 오른쪽 줄의 윗쪽 숫자를 아래로 옮김
				Pos next = new Pos(temp.x-1, temp.y);
				nMap[temp.x][temp.y] = nMap[next.x][next.y];
				temp = next;
			}
			for(int j=1; j<= i*2 - 1; j++) { // 윗쪽 줄의 왼쪽 숫자를 오른쪽으로 옮김
				Pos next = new Pos(temp.x, temp.y-1);
				nMap[temp.x][temp.y] = nMap[next.x][next.y];
				temp = next;
			}
			nMap[start.x][start.y+1] = value; // start 한 숫자 오른쪽 자리에 start의 값을 넣음
		}
	}
	// 원 배열이 아닌 새로운 배열을 사용하기 위한 배열 복제 메소드
	static int[][] copyMap() {
		int[][] nMap = new int[N][M];
		
		for(int i=0; i<N; i++) {
			for(int j=0; j<M; j++) {
				nMap[i][j] = graph[i][j];
			}
		}
		
		return nMap;
	}
	// 열의 최솟값을 얻는 메소드
	static int sumRow(int[][] nMap) {
		int[] rowSum = new int[N];
		
		for(int i=0; i<N; i++) {
			for(int j=0; j<M; j++) {
				rowSum[i] += nMap[i][j];
			}
		}
		
		Arrays.sort(rowSum);
		
		return rowSum[0];
	}
		
	static class Pos{
		int x, y;
		
		Pos(int x, int y){
			this.x = x;
			this.y = y;
		}
	}
		
}

정리

• 입력된 조건 순서 그대로가 아니라 순열로 순서를 조합하여 회전시켜야 하는데 문제 해석을 잘 못 했다.