백준 - 배열 돌리기 4 (17406)

1. 문제

문제 링크

2. 풀이

역시 전형적인 삼성 문제 아니겠습니까?
K번 배열을 돌리는 경우에 대해 모든 순열을 탐색하고 그 중 배열의 최솟값을 찾으면 됩니다.

계획1 - K번 배열을 돌리는 모든 경우를 탐색합니다.

for (int i = 0; i < K; i++) {
	if (picked[i]) continue;
	
	// 백트래킹 영역
	picked[i] = true;
	rotate(i, tmp); // i번째의 명령으로 회전
	ret = Math.min(ret, min(depth + 1)); // 다음 재귀 호출
	copy(A, tmp); // 다시 되돌리기
	picked[i] = false;
}

⚾ 포스팅에서도 보았듯이 순열을 만들려면 위와 같은 방식으로 하면 됩니다.

계획2 - 배열의 회전을 구현합니다.

static void rotate(int nth, int[][] tmp) {
	int[] v = list.get(nth);
	int y = v[0];
	int x = v[1];
	int s = v[2];
	
	// 바깥쪽부터 안쪽까지 총 s개의 테두리를 회전시킵니다.
	for (int i = 1; i <= s; i++) {
		// 시작 변수 세팅
		int sy = y - i; 
		int sx = x - i;
		
		// 동, 남, 서, 북 방향대로 차례대로 회전 구현
		for (int dir = 0; dir < 4; dir++) {
			while (true) {
				int ny = sy + my[dir];
				int nx = sx + mx[dir];
				
				// 이동 시키기
				A[ny][nx] = tmp[sy][sx];
				
				// 다음 위치 세팅
				sy = ny;
				sx = nx;
				
				// 동쪽으로 이동시키면서 오른쪽 끝에 다다르거나,
				// 남쪽으로 이동시키면서 아래쪽 끝에 다다르거나,
				// 서쪽으로 이동시키면서 왼쪽 끝에 다다르거나,
				// 북쪽으로 이동시키면서 위쪽 끝에 다다를 때 break
				if ((dir == 0 && nx == x + i) || (dir == 1 && ny == y + i) ||
						(dir == 2 && nx == x - i) || (dir == 3 && ny == y - i)) break;
			}
		}
	}
}

미세먼지 안녕! 포스팅에서 공기청정기를 가동하는 코드의 컨셉 그대로 가져와서 구현했습니다.

계획3 - K번 돌렸을 때 배열의 최솟값을 구합니다.

// 기저 사례 - k번 회전을 시켰을 때
if (depth == K) {
	int ret = MAX;
	
	// 모든 row에 대해 최솟값을 리턴
	for (int i = 0; i < N; i++) {
		int sum = 0;
		for (int j = 0; j < M; j++)
			sum += A[i][j];
		
		ret = Math.min(ret, sum);
	}
	
	return ret;
}

모든 재료가 갖추어졌습니다.
이제 이들을 이용하면 정답을 구할 수 있습니다.

3. 전체 코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class Main {
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
	static final int MAX = 987654321;
	static int N, M, K, A[][];
	static int[] my = {0, 1, 0, -1}, mx = {1, 0, -1, 0}; // 동, 남, 서, 북
	static ArrayList<int[]> list = new ArrayList<>();
	static boolean[] picked;
	
	static int min(int depth) {
		// 기저 사례 - k번 회전을 시켰을 때
		if (depth == K) {
			int ret = MAX;
			
			// 모든 row에 대해 최솟값을 리턴
			for (int i = 0; i < N; i++) {
				int sum = 0;
				for (int j = 0; j < M; j++)
					sum += A[i][j];
				
				ret = Math.min(ret, sum);
			}
			
			return ret;
		}
		
		int[][] tmp = new int[N][M];
		int ret = MAX;
		
		// 이전 상태를 기억하는 배열 세팅
		copy(tmp, A);
		
		for (int i = 0; i < K; i++) {
			if (picked[i]) continue;
			
			// 백트래킹 영역
			picked[i] = true;
			rotate(i, tmp); // i번째의 명령으로 회전
			ret = Math.min(ret, min(depth + 1)); // 다음 재귀 호출
			copy(A, tmp); // 다시 되돌리기
			picked[i] = false;
		}
		
		return ret;
	}
	
	// 배열의 회전
	static void rotate(int nth, int[][] tmp) {
		int[] v = list.get(nth);
		int y = v[0];
		int x = v[1];
		int s = v[2];
		
		// 바깥쪽부터 안쪽까지 총 s개의 테두리를 회전시킵니다.
		for (int i = 1; i <= s; i++) {
			// 시작 변수 세팅
			int sy = y - i; 
			int sx = x - i;
			
			// 동, 남, 서, 북 방향대로 차례대로 회전 구현
			for (int dir = 0; dir < 4; dir++) {
				while (true) {
					int ny = sy + my[dir];
					int nx = sx + mx[dir];
					
					// 이동 시키기
					A[ny][nx] = tmp[sy][sx];
					
					// 다음 위치 세팅
					sy = ny;
					sx = nx;
					
					// 동쪽으로 이동시키면서 오른쪽 끝에 다다르거나,
					// 남쪽으로 이동시키면서 아래쪽 끝에 다다르거나,
					// 서쪽으로 이동시키면서 왼쪽 끝에 다다르거나,
					// 북쪽으로 이동시키면서 위쪽 끝에 다다를 때 break
					if ((dir == 0 && nx == x + i) || (dir == 1 && ny == y + i) ||
							(dir == 2 && nx == x - i) || (dir == 3 && ny == y - i)) break;
				}
			}
		}
	}
	
	static void copy(int[][] a, int[][] b) {
		for (int i = 0; i < N; i++)
			for (int j = 0; j < M; j++)
				a[i][j] = b[i][j];
	}
	
	public static void main(String[] args) throws Exception {
		String[] s = br.readLine().split(" ");
		N = Integer.parseInt(s[0]);
		M = Integer.parseInt(s[1]);
		K = Integer.parseInt(s[2]);
		
		A = new int[N][M];
		picked = new boolean[K];
		
		for (int i = 0; i < N; i++) {
			s = br.readLine().split(" ");
			for (int j = 0; j < M; j++)
				A[i][j] = Integer.parseInt(s[j]);
		}
		
		for (int i = 0; i < K; i++) {
			s = br.readLine().split(" ");
			list.add(new int[] {
				Integer.parseInt(s[0]) - 1,
				Integer.parseInt(s[1]) - 1,
				Integer.parseInt(s[2])
			});
		}
		
		bw.write(min(0) + "");
		bw.close();
	}
}

삼성 기출 문제는 백트래킹과 높은 구현력을 요구하는 문제가 많기 때문에
백트래킹의 높은 숙달력은 필수입니다.