🧩 문제
크기가 N×M 크기인 배열 A가 있을때, 배열 A의 값은 각 행에 있는 모든 수의 합 중 최솟값을 의미한다. 배열 A가 아래와 같은 경우 1행의 합은 6, 2행의 합은 4, 3행의 합은 15이다. 따라서, 배열 A의 값은 4이다.
1 2 3
2 1 1
4 5 6배열은 회전 연산을 수행할 수 있다. 회전 연산은 세 정수 (r, c, s)로 이루어져 있고, 가장 왼쪽 윗 칸이 (r-s, c-s), 가장 오른쪽 아랫 칸이 (r+s, c+s)인 정사각형을 시계 방향으로 한 칸씩 돌린다는 의미이다. 배열의 칸 (r, c)는 r행 c열을 의미한다.
예를 들어, 배열 A의 크기가 6×6이고, 회전 연산이 (3, 4, 2)인 경우에는 아래 그림과 같이 회전하게 된다.
회전 연산이 두 개 이상이면, 연산을 수행한 순서에 따라 최종 배열이 다르다.
다음은 배열 A의 크기가 5×6이고, 회전 연산이 (3, 4, 2), (4, 2, 1)인 경우의 예시이다.
배열 A에 (3, 4, 2), (4, 2, 1) 순서로 연산을 수행하면 배열 A의 값은 12, (4, 2, 1), (3, 4, 2) 순서로 연산을 수행하면 15 이다.
배열 A와 사용 가능한 회전 연산이 주어졌을 때, 배열 A의 값의 최솟값을 구해보자. 회전 연산은 모두 한 번씩 사용해야 하며, 순서는 임의로 정해도 된다.
입력
첫째 줄에 배열 A의 크기 N, M, 회전 연산의 개수 K가 주어진다.
둘째 줄부터 N개의 줄에 배열 A에 들어있는 수 A[i][j]가 주어지고, 다음 K개의 줄에 회전 연산의 정보 r, c, s가 주어진다.
출력
배열 A의 값의 최솟값을 출력한다.
제한
예제
입력
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출력
12🎯 풀이
| 메모리 | 시간 | 코드길이 |
|---|---|---|
| 22140 KB | 244 ms | 4639 B |
Point
- 회전 연산은 모두 다 사용하되 순서는 임의로 정해도 되므로
순열을 사용한다.- 배열을 돌릴 때 구현에 실수하지 않도록 주의하고
재귀를 이용하여 안쪽의 사각형의 배열도 돌려준다.
1. 객체 준비 및 선언
private static class Rotate {
int r, c, s;
public Rotate(int r, int c, int s) {
this.r = r;
this.c = c;
this.s = s;
}
}회전 연산을 저장할 rotates 배열을 만든 후 순열을 이용하여 순서를 정한다.
2. 순열
private static void perm(int cnt) {
if(cnt == K) {
copy(); //회전 시킬 배열복사본 생성
for(int i = 0; i < K; i++) {
int r = selectedRotates[i].r;
int c = selectedRotates[i].c;
int s = selectedRotates[i].s;
doRotate(r, c, s);
}
getMin();
return;
}
for(int i = 0; i < K; i++) {
if(!isSelected[i]) {
isSelected[i] = true;
selectedRotates[cnt] = rotates[i];
perm(cnt + 1);
isSelected[i] = false;
}
}
}K중에서 K개를 고르는 순열 함수를 생성한다. 순열을 이용하여 하나의 selectedRotates가 만들어질 때마다 배열을 회전시킨다. 이때, 원본의 배열을 돌리면 다음 회전이 있을 때 문제가 생기므로 원본 배열의 복사본을 생성(copy())한다.
3. 배열 돌리기
private static void doRotate(int r, int c, int s) {
if(s == 0) return; //종료 조건
int[] leftUp = {r-s, c-s};
int[] rightUp = {r-s, c+s};
int[] rightDown = {r+s, c+s};
int[] leftDown = {r+s, c-s};
int[] tmp = {copiedMap[rightUp[0]][rightUp[1]],
copiedMap[leftUp[0]][leftUp[1]],
copiedMap[leftDown[0]][leftDown[1]],
copiedMap[rightDown[0]][rightDown[1]]
};
//정사각형 윗변
for(int j = rightUp[1]; j > leftUp[1] + 1; j--) {
copiedMap[rightUp[0]][j] = copiedMap[rightUp[0]][j-1];
}
copiedMap[rightUp[0]][leftUp[1]+1] = tmp[1];
//정사각형 왼쪽변
for(int i = leftUp[0]; i < leftDown[0] - 1; i++) {
copiedMap[i][leftUp[1]] = copiedMap[i+1][leftDown[1]];
}
copiedMap[leftDown[0]-1][leftDown[1]] = tmp[2];
//정사각형 밑변
for(int j = leftDown[1]; j < rightDown[1] - 1; j++) {
copiedMap[leftDown[0]][j] = copiedMap[rightDown[0]][j+1];
}
copiedMap[rightDown[0]][rightDown[1]-1] = tmp[3];
//정사각형 오른쪽 변
for(int i = rightDown[0]; i > rightUp[0] + 1; i--) {
copiedMap[i][rightDown[1]] = copiedMap[i-1][rightUp[1]];
}
copiedMap[rightUp[0]+1][rightUp[1]] = tmp[0];
doRotate(r, c, s-1); //재귀를 이용하여 안쪽 배열들도 회전 시킴
}배열을 돌린다. 상하좌우 각각의 변의 마지막 값을 옮기기 위해서 tmp[] 배열을 사용했으며 이곳에는 사각형 각 꼭짓점의 값들이 들어있다.
가장 외곽의 사각형 뿐만 아니라 내부의 사각형들도 회전시켜야하므로 재귀를 통하여 구현하였다. 재귀로 들어갈 때에는 s-1으로 파라미터를 넘겨주어 하나 더 작은 사각형을 회전시키게하였으며, 종료조건은 s의 값이 0일 경우로 하였다.
4. 행의 최소 합 찾기
private static void getMin() {
for(int i = 0; i < copiedMap.length; i++) {
int sum = 0;
for(int j = 0; j < copiedMap[i].length; j++) {
sum += copiedMap[i][j];
}
answer = Integer.min(answer, sum);
}
}각 행에 있는 숫자들을 모두 합하여 answer값과 비교하여 더 작은 수를 answer에 삽입한다.
⭐️ 전체 풀이 코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class BJ17406_배열돌리기4 {
private static int N, M, K, answer = Integer.MAX_VALUE;
private static boolean isSelected[];
private static Rotate[] rotates, selectedRotates;
private static int[][] map, copiedMap;
private static class Rotate {
int r, c, s;
public Rotate(int r, int c, int s) {
this.r = r;
this.c = c;
this.s = s;
}
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken()); //배열의 행
M = Integer.parseInt(st.nextToken()); //배열의 열
K = Integer.parseInt(st.nextToken()); //회전 연산의 개수
map = new int[N][M];
copiedMap = new int[N][M];
rotates = new Rotate[K];
selectedRotates = new Rotate[K];
isSelected = new boolean[K];
//배열에 입력
for(int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine());
for(int j = 0; j < M; j++) {
map[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());
rotates[i] = new Rotate(r, c, s);
}
//회전 연산은 모두 한 번씩 사용해야 하며, 순서는 임의로 정해도 되므로 순열을 이용하여 순서 정하기
perm(0);
System.out.println(answer);
} //main 끝
private static void getMin() {
for(int i = 0; i < copiedMap.length; i++) {
int sum = 0;
for(int j = 0; j < copiedMap[i].length; j++) {
sum += copiedMap[i][j];
}
answer = Integer.min(answer, sum);
}
}
private static void doRotate(int r, int c, int s) {
if(s == 0) return; //종료 조건
int[] leftUp = {r-s, c-s};
int[] rightUp = {r-s, c+s};
int[] rightDown = {r+s, c+s};
int[] leftDown = {r+s, c-s};
int[] tmp = {copiedMap[rightUp[0]][rightUp[1]],
copiedMap[leftUp[0]][leftUp[1]],
copiedMap[leftDown[0]][leftDown[1]],
copiedMap[rightDown[0]][rightDown[1]]
};
//정사각형 윗변
for(int j = rightUp[1]; j > leftUp[1] + 1; j--) {
copiedMap[rightUp[0]][j] = copiedMap[rightUp[0]][j-1];
}
copiedMap[rightUp[0]][leftUp[1]+1] = tmp[1];
//정사각형 왼쪽변
for(int i = leftUp[0]; i < leftDown[0] - 1; i++) {
copiedMap[i][leftUp[1]] = copiedMap[i+1][leftDown[1]];
}
copiedMap[leftDown[0]-1][leftDown[1]] = tmp[2];
//정사각형 밑변
for(int j = leftDown[1]; j < rightDown[1] - 1; j++) {
copiedMap[leftDown[0]][j] = copiedMap[rightDown[0]][j+1];
}
copiedMap[rightDown[0]][rightDown[1]-1] = tmp[3];
//정사각형 오른쪽 변
for(int i = rightDown[0]; i > rightUp[0] + 1; i--) {
copiedMap[i][rightDown[1]] = copiedMap[i-1][rightUp[1]];
}
copiedMap[rightUp[0]+1][rightUp[1]] = tmp[0];
doRotate(r, c, s-1); //재귀를 이용하여 안쪽 배열들도 회전 시킴
}
private static void copy() {
int tmp = 0;
for(int i = 0; i < N; i++) {
for(int j = 0; j < M; j++) {
tmp = map[i][j];
copiedMap[i][j] = tmp;
}
}
}
private static void perm(int cnt) {
if(cnt == K) {
copy(); //회전 시킬 배열복사본 생성
for(int i = 0; i < K; i++) {
int r = selectedRotates[i].r;
int c = selectedRotates[i].c;
int s = selectedRotates[i].s;
doRotate(r, c, s);
}
getMin();
return;
}
for(int i = 0; i < K; i++) {
if(!isSelected[i]) {
isSelected[i] = true;
selectedRotates[cnt] = rotates[i];
perm(cnt + 1);
isSelected[i] = false;
}
}
}
}
느낀 점
배열을 돌리기를 잘 해내어놓고 순열에서
if(!isSelected[i])조건을 빼먹었다. 코드 사이사이에서 값들을 출력해보고나서야 순열에서 틀렸다는 것을 발견했는데 한번 작성할 때 꼼꼼하게 작성해야 함을 다시 한번 느꼈다.
봉다리