출처: https://www.acmicpc.net/problem/17406
Input
5 6 2
1 2 3 2 5 6
3 8 7 2 1 3
8 2 3 1 4 5
3 4 5 1 1 1
9 3 2 1 4 3
3 4 2
4 2 1
Output
12
회전 연산]
6 x 6 배열과 (r, c, s) = (3, 4, 2) 일 때,
좌측 상단: (r-s, c-s) / 우측 하단: (r+s, c+s)
『배열 A의 값』은 각 행에 있는 모든 수의 합 중 최솟값을 의미.
주어진 회전을 순서로 임의로 배정했을 때, 『배열 A의 값』 중 최소값을 구하는 문제입니다.
구현 순서
① 모든 회전 가능한 회전 경우의 수 구현 ← 순열
② 회전 순서가 정해지면 배열 내부에서 특정 영역(정사각형)에 대한 회전(재배치)
회전(재배치)을 시켜서 배열 A의 최솟값을 구합니다.
기준점을 좌측 상단 『1』을 기점으로 {테두리 길이 - 1} 만큼 순회합니다.
따라서, List = {2, 3, 4, 9, 14, 19, 18, 17, 16, 11, 6, 1} 담습니다.
맨 마지막 원소를 제일 앞에 둬서 List = {1, 2, 3, 4, 9, 14, 19, 18, 17, 16, 11, 6}
다시 배열을 순회하여 원소를 재할당하여 회전한 것처럼 구현합니다.
마찬가지로, 안쪽 테두리도 기준점을 『7』로 해서 동일한 작업을 반복합니다.
(이때, 테두리 길이는 {이전 길이 -2} 입니다.)
→ : 기준점『0』 / 테두리 길이 = 5
→ : 기준점『6』 / 테두리 길이 = 3
→ : 기준점 『12』 / 테두리 길이 = 1
③ 주어진 회전 연산이 끝나면, 문제에서 배열 A의 값 중 최솟값을 구합니다.
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
public class Main {
static int[][] arr;
static List<Rotate> list;
static List<Rotate> rotateOrder;
static boolean[] visited;
static int N, M, K;
static int answer = Integer.MAX_VALUE;
static class Rotate{
int ID;
int r, c, s;
public Rotate(int r, int c, int s, int ID) {
this.r = r;
this.c = c;
this.s = s;
this.ID = ID;
}
@Override
public String toString() {
return "[" + ID + "] ";
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
N = Integer.parseInt(sc.next());
M = Integer.parseInt(sc.next());
K = Integer.parseInt(sc.next());
arr = new int[N+1][M+1];
for(int i=1; i<=N; i++) {
for(int j=1; j<=M; j++) {
arr[i][j] = Integer.parseInt(sc.next());
}
}
list = new ArrayList<>();
for(int i=0; i<K; i++) {
list.add(new Rotate(
Integer.parseInt(sc.next()), // r
Integer.parseInt(sc.next()), // c
Integer.parseInt(sc.next()), // s
i // ID
));
}
visited = new boolean[K];
rotateOrder = new ArrayList<>();
perm();
System.out.println(answer);
}
private static void perm() {
if(rotateOrder.size() == K) {
rotate(deepCopy(arr), rotateOrder);
return;
}
for(int i=0; i<K; i++) {
// 방문하지 않은 곳이라면
if(!visited[i]) {
rotateOrder.add(list.get(i));
visited[i] = true;
perm();
rotateOrder.remove(rotateOrder.size()-1);
visited[i] = false;
}
}
}
private static int[][] deepCopy(int[][] src) {
int[][] dest = new int[N+1][M+1];
for(int i=1; i<=N; i++) {
System.arraycopy(src[i], 0, dest[i], 0, src[i].length);
}
return dest;
}
private static void rotate(int[][] arr, List<Rotate> rotateOrder) {
// 주어진 회전 순서만큼
for(int r=0; r<rotateOrder.size(); r++) {
// 왼쪽 상단의 기준점
Rotate obj = rotateOrder.get(r);
int x = obj.r - obj.s;
int y = obj.c - obj.s;
// 최초 바깥쪽 테두리의 길이
int len = (obj.s * 2) + 1;
// 우, 하, 좌, 상(감싸는 방향)
int[] dx = {0, 1, 0, -1};
int[] dy = {1, 0, -1, 0};
List<Integer> temp = new ArrayList<>();
while(true) {
for(int i=0; i<4; i++) {
// 할당된 테두리만큼 원소를 리스트에 담는다.
for(int l=1; l<len; l++) {
x = x + dx[i];
y = y + dy[i];
temp.add(arr[x][y]);
}
}
// 한 번 회전환 순서로 배치
temp.add(0, temp.remove(temp.size()-1));
// 재배치된 숫자를 다시 해당 테두리에 할당
for(int i=0; i<4; i++) {
// 할당된 테두리만큼 원소를 리스트에 담는다.
for(int l=1; l<len; l++) {
x = x + dx[i];
y = y + dy[i];
arr[x][y] = temp.remove(0);
}
}
// 테두리 반경 줄여나가기
len = len - 2;
// 기준점도 따라서 재설정
x++; y++;
// 회전할 필요가 없을 때까지
// 짝수로 시작했으면 0 / 홀수로 시작했으면 1
if (len == 0 || len == 1) break;
}
}
// 각각의 회전 순서 중 최솟값
answer = Math.min(answer, solve(arr));
}
// 주어진 회전 순서에서 배열의 최솟값
private static int solve(int[][] arr) {
int temp = Integer.MAX_VALUE;
for(int i=1; i<=N; i++) {
int sum = 0;
for(int j=1; j<=M; j++) {
sum += arr[i][j];
}
temp = Math.min(temp, sum);
}
return temp;
}
}
'PS 문제 풀이 > Baekjoon' 카테고리의 다른 글
[BOJ] 백준 17135 캐슬 디펜스 (0) | 2021.02.22 |
---|---|
[BOJ] 백준 4355 서로소 (0) | 2021.02.22 |
[BOJ] 백준 1786 찾기 (0) | 2021.02.22 |
[BOJ] 백준 1120 문자열 (0) | 2021.02.22 |
[BOJ] 백준 14620 꽃길 (0) | 2021.02.22 |
댓글