[BOJ/Java] 17406 : 배열 돌리기4

문제

 

풀이

1. 처음에 문제를 잘 안 읽어서 틀렸다. 입력 받은 순서대로 회전 후 값을 출력하는 게 아니라 입력 받은 좌표 중에서 모든 순서대로 결과를 뽑은 다음에 그 중 최솟값을 출력하는 문제이다. 
2. 회전해야 할 좌표에 대한 정보 K개를 배열에 넣는다
3. 회전 정보 K개 만큼의 순열을 생성해 어떤 순서로 회전할 지 정한다
4. 만들어진 순열을 바탕으로 회전한다
5. 배열 A의 값을 구한다
6. 다시 3으로 돌아간다
7. 모든 순열에 대해 배열 A의 값을 비교해 최솟값을 출력한다

 

배열을 회전할 때는 중간 좌표인 A[3][4]를 기준으로 S값 만큼 for문을 돌려 A[3-i][4-i] 부터 시작해 회전하도록 구현했다.

 

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main { // 배열 돌리기 4
	static BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
	static StringTokenizer st;
	static int[][] dir = { { 1, 0 }, { 0, 1 }, { -1, 0 }, { 0, -1 } };
	static int N, M, K;
	static int midX, midY, s;
	static int[][] arr;
	static int[][] original;
	static int[][] rcs;
	static int result = Integer.MAX_VALUE; //모든 경우를 다 비교했을 때 가장 작은 A값

	
	static void calculateMinSum() {
		int minSum = Integer.MAX_VALUE;
		for (int i = 1; i <= N; i++) {
			int sum = 0;
			for (int j = 1; j <= M; j++) {
				sum += arr[i][j];
			}
			minSum = Math.min(minSum, sum);
		}
		
		result = Math.min(result, minSum);
		minSum = Integer.MAX_VALUE;
		
		for (int i = 1; i <= N; i++) {
			for (int j = 1; j <= M; j++) {
				arr[i][j] = original[i][j];
			}
		}
	}

	static void permutation(int[] array, int depth, int r) {
		if (depth == r) {
			for (int i = 0; i < r; i++) {
				midX = rcs[array[i]][0];
				midY = rcs[array[i]][1];
				s = rcs[array[i]][2];
				rotate();
			}
			calculateMinSum();

			return;
		}

		for (int i = depth; i < array.length; i++) {
			int tmp = array[depth];
			array[depth] = array[i];
			array[i] = tmp;

			permutation(array, depth + 1, r);

			// 스왑한거 다시 되돌리기
			array[i] = array[depth];
			array[depth] = tmp;
		}
	}

	public static void rotate() {
		for (int i = 1; i <= s; i++) {
			int direction = 0;
			int dx = midX - i;
			int dy = midY - i;
			int temp = arr[dx][dy];
			while (direction != 4) {
				int nextX = dx + dir[direction][0];
				int nextY = dy + dir[direction][1];
				if (nextX < midX - i || nextY < midY - i || nextX > midX + i || nextY > midY + i) {
					direction++;
				} else {
					arr[dx][dy] = arr[nextX][nextY];
					dx = nextX;
					dy = nextY;
				}

			}
			arr[midX - i][midY - i + 1] = temp;

		}

	}

	public static void main(String[] args) throws Exception {

		st = new StringTokenizer(in.readLine(), " ");
		N = Integer.parseInt(st.nextToken()); // 행
		M = Integer.parseInt(st.nextToken()); // 열
		K = Integer.parseInt(st.nextToken()); // 회전 연산 개수
		arr = new int[N + 1][M + 1];

		for (int i = 1; i <= N; i++) { // 배열에 초기값을 입력받음
			st = new StringTokenizer(in.readLine(), " ");
			for (int j = 1; j <= M; j++) {
				arr[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		rcs = new int[K][3];
		for (int i = 0; i < K; i++) {
			st = new StringTokenizer(in.readLine());

			rcs[i][0] = Integer.parseInt(st.nextToken());
			rcs[i][1] = Integer.parseInt(st.nextToken());
			rcs[i][2] = Integer.parseInt(st.nextToken());
		}
		// 순열 만들기 ( Next_permutation)
		int[] np = new int[K];
		for (int i = 0; i < K; i++) {
			np[i] = i;
		}
		original = new int[N+1][M+1];
		for (int i = 1; i <= N; i++) {
			for (int j = 1; j <= M; j++) {
				original[i][j] = arr[i][j];
			}
		}

		permutation(np, 0, K);
		
		System.out.println(result);

	}

}

 

느낀점

순열은 빨랑빨랑 구현하자