백준 17406번: 배열 돌리기 4

문제 설명

• 2차원 배열을 다루는 문제입니다.

접근법

• 필요한 개념

  • 배열 회전
  • 순열
  • 2차원 배열의 값복사 (주소복사X)

• 배열을 회전하는 방법

  • 회전순서(오른쪽,아래,왼쪽,위)를 값으로 설정합니다.
    • dx = { 0, 1, 0, -1 };
    • dy = { 1, 0, -1, 0 };
  • 다음 순서로 넘어갈 수 있는지를 확인합니다. 넘어갈 수 없다면 방향을 바꿉니다.
    • if (start_i > x + dx[d] || x + dx[d] > end_i || start_j > y + dy[d] || y + dy[d] > end_j) d = (d + 1) % 4;
  • 좌표를 업데이트 합니다.
    • int nx = x + dx[d];
    • int ny = y + dy[d];
  • 값을 업데이트 합니다.
    • new_board[nx][ny] = t_board[x][y];
    • x = nx;
    • y = ny;

pseudocode

main(){
lst에 회전 연산의 정보 담기.
순열 실행하기.
}
순열(){ //K개의 명령값을 줄세우는 순열
	if(순열이 완성되면){
    순열의 순서대로 lst에거 값을 꺼냅니다.
    꺼낸 값의 순서대로 배열을 돌립니다.
    최종 배열로 점수를 계산합니다.
    }
}
배열 돌리기(){
	복사본 배열을 만듭니다.
	while(배열 속에 돌릴 수 있는 다음 배열이 있는 동안){
    	if(다음 원소가 배열의 범위를 벗어나면) 방향을 변경합니다.
	    해당 방향으로의 다음좌표를 구합니다.
        복사본 배열의 다음좌표값에 입력받은 배열의 현재좌표값을 넣습니다.
        좌표를 업데이트 시킵니다.
    }
}

정답

import java.util.*;

public class Main {
	static int N;
	static int M;
	static int K;
	static int[][] board;
	static boolean[] v;
	static int[] num;
	static List<int[]> lst;
	static int min_num = Integer.MAX_VALUE;

	public static void main(String[] args) {
		// 입력값 처리
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt();
		M = sc.nextInt();
		K = sc.nextInt();
		board = new int[N][M];
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				board[i][j] = sc.nextInt();
			}
		}
		// 순열을 만들때 활용되는 변수
		v = new boolean[K];
		num = new int[K];
		
		lst = new ArrayList<int[]>(); // 회전 연산의 정보가 담기는 리스트

		for (int k = 0; k < K; k++) {
			int r = sc.nextInt();
			int c = sc.nextInt();
			int s = sc.nextInt();
			int[] temp = { r, c, s };
			lst.add(temp);
		}
		permu(0);
		System.out.println(min_num);

	}

	public static void permu(int depth) { 
		if (depth == K) {
			// 매 순열마다 원본배열과 동일한 배열을 가져옵니다.
			int[][] temp_board = new int[N][M];
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < M; j++) {
					temp_board[i][j] = board[i][j];
				}
			}

			// 순열의 순서대로 배열을 돌립니다.
			for (int k = 0; k < K; k++) {
				int[] temp = lst.get(num[k]);
				temp_board = turn(temp[0], temp[1], temp[2], temp_board);
			}
			// 점수를 계산합니다.
			score(temp_board);

			return;
		}

		for (int i = 0; i < K; i++) {
			// visited를 확인할 때 사용되는 변수는 depth가 아니라 i입니다. 
			if (v[i]) continue; 
			v[i] = true;
			num[depth] = i;
			permu(depth + 1);
			v[i] = false;
		}
	}

	public static int[][] turn(int r, int c, int s, int[][] t_board) {
		int[][] temp_board = func(r - s - 1, r + s - 1, c - s - 1, c + s - 1, t_board);
		return temp_board;

	}

	public static int[][] func(int start_i, int end_i, int start_j, int end_j, int[][] t_board) {
		// 원본 배열을 보존하기 위해 복사본 배열을 만듭니다.
		int[][] new_board = new int[N][M];
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				new_board[i][j] = t_board[i][j];
			}
		}

		while (start_i < end_i && start_j < end_j) { // 회전할 부분의 겉에서부터 안쪽까지 모두 돌립니다.
			// while문이 한 번 실행될때마다 겉의 값들이 회전됩니다.			
			int cnt = (end_i - start_i + 1) * (end_j - start_j + 1); // 배열의 겉면 원소가 몇 개인지를 나타냅니다.
			int[] dx = { 0, 1, 0, -1 };
			int[] dy = { 1, 0, -1, 0 };
			int d = 0;
			int x = start_i;
			int y = start_j;
			for (int c = 0; c < cnt; c++) { // 배열의 겉면 원소의 개수만큼 값을 변경시켜 줍니다.
				// 배열을 벗어나면 방향을 변경시켜 줍니다.
				if (start_i > x + dx[d] || x + dx[d] > end_i || start_j > y + dy[d] || y + dy[d] > end_j) d = (d + 1) % 4;
				int nx = x + dx[d];
				int ny = y + dy[d];
				new_board[nx][ny] = t_board[x][y];
				x = nx;
				y = ny;
			}
			// 회전시킨 겉면을 제외한 나머지를 다시 돌립니다.
			start_i += 1;
			end_i -= 1;
			start_j += 1;
			end_j -= 1;
		}
		return new_board;

	}

	public static void score(int[][] board) { //점수를 계산합니다.
		for (int i = 0; i < N; i++) {
			int sum = 0; 
			for (int j = 0; j < M; j++) {
				sum += board[i][j];
			}
			min_num = Math.min(min_num, sum);
		}
	}

}

기타

• 유사한 문제
  • 배열 돌리기
• 배열을 계속 복제해 메모리 낭비가 심합니다.