자바칩
[백준 / Java] 17406: 배열 돌리기 4 (구현, 백트래킹) 본문
난이도: Gold 4
문제: https://www.acmicpc.net/problem/17406
문제
크기가 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[1][1] A[1][2] → A[1][3] → A[1][4] → A[1][5] → A[1][6]
↑ ↓
A[2][1] A[2][2] A[2][3] → A[2][4] → A[2][5] A[2][6]
↑ ↑ ↓ ↓
A[3][1] A[3][2] A[3][3] A[3][4] A[3][5] A[3][6]
↑ ↑ ↓ ↓
A[4][1] A[4][2] A[4][3] ← A[4][4] ← A[4][5] A[4][6]
↑ ↓
A[5][1] A[5][2] ← A[5][3] ← A[5][4] ← A[5][5] ← A[5][6]
A[6][1] A[6][2] A[6][3] A[6][4] A[6][5] A[6][6]
회전 연산이 두 개 이상이면, 연산을 수행한 순서에 따라 최종 배열이 다르다.
다음은 배열 A의 크기가 5×6이고, 회전 연산이 (3, 4, 2), (4, 2, 1)인 경우의 예시이다.
| 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 |
1 8 2 3 2 5 3 2 3 7 2 6 8 4 5 1 1 3 3 3 1 1 4 5 9 2 1 4 3 1 |
1 8 2 3 2 5 3 2 3 7 2 6 3 8 4 1 1 3 9 3 5 1 4 5 2 1 1 4 3 1 |
| 배열 A | (3, 4, 2) 연산 수행 후 | (4, 2, 1) 연산 수행 후 |
| 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 |
1 2 3 2 5 6 3 8 7 2 1 3 3 8 2 1 4 5 9 4 3 1 1 1 3 2 5 1 4 3 |
1 8 2 3 2 5 3 8 2 7 2 6 3 4 3 1 1 3 9 2 1 1 4 5 3 5 1 4 3 1 |
| 배열 A | (4, 2, 1) 연산 수행 후 | (3, 4, 2) 연산 수행 후 |
배열 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의 값의 최솟값을 출력한다.
제한
- 3 ≤ N, M ≤ 50
- 1 ≤ K ≤ 6
- 1 ≤ A[i][j] ≤ 100
- 1 ≤ s
- 1 ≤ r-s < r < r+s ≤ N
- 1 ≤ c-s < c < c+s ≤ M
백트래킹은 어렵지 않으나 배열을 돌리는 구현이 어렵다..
실버3 달팽이 구현 문제도 엄청 쩔쩔매면서 풀었었다.
구현 문제를 좀 많이 풀어봐야겠다.
먼저 선언해야할 전역 변수들은 다음과 같다.
메인 메서드에서 N(세로), M(가로), K(회전 연산 개수)를 입력받고 배열을 다음과 같이 초기화할 것이다.
calcs 배열의 행은 연산 0부터 K - 1이고,
calcs 배열의 열은 r, c, s를 뜻한다.
| calcs[K][3] | 0 (r) | 1 (c) | 2 (s) |
| 0 | 3 | 4 | 2 |
| 1 | 4 | 2 | 1 |
| ... | |||
| K - 1 | 3 | 2 | 1 |
order 배열은 0번째부터 K - 1번째까지 연산 순서를 정하는 배열이다.
만약 K가 3이고 order = {1, 2, 0} 이라면
calcs[order[0]][] = calcs[1][] // 0번째로 calcs 배열에 담긴 연산 1 수행
calcs[order[1]][] = calcs[2][] // 1번째로 calcs 배열에 담긴 연산 2 수행
calcs[order[2]][] = calcs[0][] // 2번째로 calcs 배열에 담긴 연산 0 수행
와 같이 사용할 수 있다.
calcs 배열은 다음과 같이 초기화하면 된다.
그리고 dfs로 0번째 연산부터 순서를 정하러 간다.
dfs 메서드는 다음과 같다.
메서드가 좀 길다. 먼저 전형적인 백트래킹 수행 로직인 맨 아래의 for문부터 보자.
K개(0 ~ K - 1)의 연산을 모두 탐색하면서, 해당 연산 i를 방문하지 않았다면 방문 체크를 먼저 한다.
그리고 매개변수로 받은 depth로 depth번째 연산의 순서를 정해야하므로 order[depth]에 해당 연산인 i를 할당한다.
depth번째 연산의 순서를 정했으므로, depth + 1번째 연산의 순서를 정하러 dfs로 재귀 호출한다.
재귀 호출이 끝났으면 다시 depth번째로 돌아와서 연산의 순서를 다시 정해야하므로, 해당 연산 i의 방문 체크를 해제한다.
이제 dfs 메서드의 if (depth == N) 문을 보자.
이 if문은 N개의 연산 순서를 모두 정했을 때 수행된다.
spin 메서드에서 회전 연산이 모두 수행된 배열의 결과를 리턴받고,
배열 각 행의 원소들을 모두 더해서 우리가 최종적으로 구해야 할 최솟값 min을 갱신한 후 dfs 메서드를 종료시킨다.
dfs 메서드를 종료시킨 후에는 다시 K - 1번째로 돌아가서 연산의 순서를 정하러 간다.
다시 돌아가는 위치는 아까 호출했던 dfs(depth + 1);이고, 그 아래에 있는 visited[i] = false;를 수행하게 된다.
visited[i] = false;란 이미 아까 해당 연산 수행을 하고 왔으니까 false 체크하여 다시 연산 순서에 참여할 수 있게 한다는 뜻이다.
회전 연산시키는 spin 메서드를 보기 전에 구현이 어떤식으로 동작하는지 그림으로 보여주겠다.
현재 연산이 r = 3, c = 4, s = 2일 때,
맨 왼쪽 윗 칸: (r - s, c - s) = (3 - 2, 4 - 2) = (1, 2)
맨 오른쪽 아랫 칸: (r + s, c + s) = (3 + 2, 4 + 2) = (5, 6)
먼저 맨 왼쪽 위에 있는 칸(A[1][2])에 있는 값을 temp 변수에 저장시킬 것이다.
그 다음 빨간색 원의 원소부터 부터 빨간색 줄의 마지막 원소까지 차례대로 값을 변경시킨다.
여기서는 A[1][6] 자리에 A[1][5]의 값을 넣고, A[1][5] 자리에 A[1][4]의 값을 넣고 ... A[1][3] 자리에 A[1][2]의 값을 넣는다.
그 다음 파란색 원의 원소부터 부터 파란란색 줄의 마지막 원소까지 차례대로 값을 변경시킨다.
여기서는 A[1][2] 자리에 A[2][2]의 값을 넣고, A[2][2] 자리에 A[3][2]의 값을 넣고 ... A[4][2] 자리에 A[5][2]의 값을 넣는다.
그 다음 초록색 원의 원소부터 부터 초록색 줄의 마지막 원소까지 차례대로 값을 변경시킨다.
여기서는 A[5][2] 자리에 A[5][3]의 값을 넣고, A[5][3] 자리에 A[5][4]의 값을 넣고 ... A[5][5] 자리에 A[5][6]의 값을 넣는다.
그 다음 보라색 원의 원소부터 부터 보라색 줄의 마지막 원소까지 차례대로 값을 변경시킨다.
여기서는 A[5][6] 자리에 A[4][6]의 값을 넣고, A[4][6] 자리에 A[3][6]의 값을 넣고 ... A[2][6] 자리에 A[1][6]의 값을 넣는다.
마지막으로 계산의 가장 마지막 칸(맨 오른쪽 윗 칸의 바로 아랫 칸, 여기에서는 A[2][6])에 맨 처음 temp 변수에 저장해둔 값을 넣는다.
이로써 가장 바깥 쪽 네모가 회전 완료되었다.
이제 안쪽 네모를 회전시키기 위해 s를 1 감소시키고 (r - s, c - s)와 (r + s, c + s)를 다시 계산하여 위의 과정을 반복한다.
s는 0이 되기 전까지만 감소시킨다.
s가 0이면 맨 왼쪽 윗 칸과 맨 왼쪽 아랫 칸 모두 (r, s)로 똑같기 때문이다.
이 과정을 총 K번 반복해야 한다.
연산 순서는 아까 order 배열에 저장해 두었던 값으로 calcs 배열의 행에 대입해서 사용한다.
이제 spin 메서드를 보자.
copyArray 메서드에서 맨 처음에 정적 변수로 선언한 A 배열을 깊은 복사한 배열을 리턴받는다.
copyArray 메서드는 2차원 배열을 새로 선언하고, 2중 for문을 돌려서 A 배열의 원소 하나씩 차례로 리턴할 배열에 값을 복사한다.
연산의 순서를 모두 정하고, 0번째부터 K - 1번째까지의 연산은 맨 처음에 받았던 A 배열의 상태를 기준으로 수행해야 하기 때문이다.
이렇게 하지 않으면 연산을 여러번 수행할 때 배열이 뒤죽박죽 되어서 원하는 결과를 얻지 못하게 된다.
전체 코드
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
|
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class P17406_배열돌리기4 {
static int N, M; // 배열의 세로, 가로 길이
static int K; // 회전 연산의 개수
static int[][] A; // 2차원 배열
static int[][] calcs; // 2차원 회전 연산 배열
static int[] order; // 1차원 회전 연산의 순서 배열
static boolean[] visited; // 1차원 방문 체크 배열
static int min = Integer.MAX_VALUE; // 배열 값의 최솟값
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());
A = new int[N + 1][M + 1];
calcs = new int[K][3];
order = new int[K];
visited = new boolean[K];
// 2차원 배열 초기화
for (int i = 1; i <= N; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 1; j <= M; j++) {
A[i][j] = Integer.parseInt(st.nextToken());
}
}
for (int i = 0; i < K; i++) {
st = new StringTokenizer(br.readLine());
int r = Integer.parseInt(st.nextToken()); // 연산의 행
int c = Integer.parseInt(st.nextToken()); // 연산의 열
// 연산을 수행할 가장 왼쪽 윗 칸: (r - s, c - s)
// 연산을 수행할 가장 오른쪽 아랫 칸: (r + s, c + s)
int s = Integer.parseInt(st.nextToken());
calcs[i][0] = r; // i번째 연산의 r
calcs[i][1] = c; // i번째 연산의 c
calcs[i][2] = s; // i번째 연산의 s
}
dfs(0); // 0번째 연산부터 순서 정하기
System.out.println(min);
}
// depth번째 연산의 순서를 정하는 메서드
public static void dfs(int depth) {
// 현재 깊이 depth가 연산 개수 K와 같다면 K개 연산들의 순서를 모두 정한 것
if (depth == K) {
int[][] copy = spin(); // 연산을 수행한 배열 리턴받기
for (int i = 1; i <= N; i++) {
int sum = 0; // 배열의 i번째 행의 합(= 배열 값)
// 배열의 i번째 행에 있는 원소들을 더하기
for (int j = 1; j <= M; j++) {
sum += copy[i][j];
}
min = Math.min(min, sum); // 배열 값의 최솟값 갱신
}
// K개의 연산을 모두 수행했으므로 K - 1번째로 다시 돌아가서 연산의 순서 정하러 가기
return;
}
// K개의 연산 모두 탐색
for (int i = 0; i < K; i++) {
// 해당 연산을 방문하지 않았다면 (해당 연산의 순서가 정해지지 않았다면)
if (!visited[i]) {
visited[i] = true; // 해당 연산 방문 체크
order[depth] = i; // 해당 연산의 순서를 depth번째로 정하기
dfs(depth + 1); // depth + 1번째 연산의 순서를 정하러 가기
visited[i] = false; // 해당 연산 방문 해제
}
}
}
// 배열을 K개의 연산만큼 회전시키는 메서드
public static int[][] spin() {
int[][] copy = copyArray(); // 원본 배열을 복사한 배열 리턴받기
// K개의 연산 모두 수행
for (int k = 0; k < K; k++) {
int r = calcs[order[k]][0]; // order[k]번째 연산의 행
int c = calcs[order[k]][1]; // order[k]번째 연산의 열
int S = calcs[order[k]][2];
// s를 1까지 1씩 감소시키면서 가장 왼쪽 윗 칸과 가장 오른쪽 아랫 칸 갱신
for (int s = S; s > 0; s--) {
int startX = r - s; // 연산을 수행할 가장 왼쪽 윗 칸의 x좌표
int startY = c - s; // 연산을 수행할 가장 왼쪽 윗 칸의 y좌표
int endX = r + s; // 연산을 수행할 가장 오른쪽 아랫 칸의 x좌표
int endY = c + s; // 연산을 수행할 가장 오른쪽 아랫 칸의 y좌표
// 가장 왼쪽 윗 칸을 임시 변수에 저장해두기
// => 연산 가장 마지막 칸을 임시 변수 값으로 교체할 예정
int temp = copy[startX][endY];
// 오른쪽 윗 칸부터 왼쪽 윗 칸까지 차례로 값을 교체
for (int i = endY; i > startY; i--) {
copy[startX][i] = copy[startX][i - 1];
}
// 왼쪽 윗 칸부터 왼쪽 아랫 칸까지 차례로 값을 교체
for (int i = startX; i < endX; i++) {
copy[i][startY] = copy[i + 1][startY];
}
// 왼쪽 아랫 칸부터 오른쪽 아랫 칸까지 차례로 값을 교체
for (int i = startY; i < endY; i++) {
copy[endX][i] = copy[endX][i + 1];
}
// 오른쪽 아랫 칸부터 오른쪽 윗 칸까지 차례로 값을 교체
for (int i = endX; i > startX; i--) {
copy[i][endY] = copy[i - 1][endY];
}
// 연산 가장 마지막 칸(오른쪽 윗 칸의 바로 아래에 있는 칸)을
// 맨 처음에 저장해 둔 임시 변수로 교체
copy[startX + 1][endY] = temp;
}
}
return copy; // 회전 연산 완료한 배열 리턴
}
// 원본 배열을 복사한 배열을 리턴하는 메서드
public static int[][] copyArray() {
int[][] copy = new int[N + 1][M + 1];
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= M; j++) {
copy[i][j] = A[i][j];
}
}
return copy;
}
}
|
cs |
'알고리즘 > 백준' 카테고리의 다른 글
| [백준 / Java] 1339: 단어 수학 (그리디) (0) | 2024.08.02 |
|---|---|
| [백준 / Java] 13904: 과제 (그리디) (0) | 2024.08.02 |
| [백준 / Java] 2023: 신기한 소수 (백트래킹) (0) | 2024.07.21 |
| [백준 / Java] 1759: 섬의 개수 (BFS) (0) | 2024.07.20 |
| [백준 / Java] 1759: 암호 만들기 (백트래킹) (1) | 2024.07.19 |
