백준 1006번: 습격자 초라기 Java Solution
1. Problem Definition & Analysis
2차원 배열(모든 구역의 집합)을 순회한다. 한 번에 최대 2개의 구역을 커버할 수 있는데 이러한 커버링의 최소 횟수를 구하는 문제이다. Top-down DP 기법을 활용할 것이므로 DFS를 수행하면서 현재의 상태(DFS 메서드의 매개변수 집합)에 따른 결과 값(최소 커버링 횟수)을 캐싱할 것이다. 이 문제에는 주의해야 할 요소가 다양하게 있다. 그래서 순차적으로 과정을 하나씩 분석해 보고자 한다.
1-1. DFS Design
현재 상태가 다음의 상태들과 충돌하지 않도록 방문 순서와 매개변수를 결정해야 한다. 다양한 구현 방법이 있겠으나 나는 다음과 같이 방문 순서 및 매개변수 집합을 결정했다.
일단 위와 같이 모든 구역의 집합을 단순화해 2행 5열의 배열로 생각해 보자. DFS 로직을 설계할 때는 문제 조건 중 원형으로 구역이 이어져 있다는 조건은 생각하지 않도록 한다.
방문 순서는 위와 같이 column-major order로 정의했다. 일단 여기서 행 번호, 열 번호가 매개변수로 지정되어야 함을 알 수 있다.
다음으로는 2번 구역과 기준점으로 삼아 커버링 방법(소대가 구역을 점령하는 방법)을 정의해 보겠다. 현재 2번 구역을 방문할 차례이고, 특수 소대가 해당 구역(및 인접 구역)을 어떻게 점령할 수 있을지와 그 이후에 어떻게 방문을 진행할 수 있을지 생각해 보자.
첫 번째 커버링 방법
첫 번째, 해당 구역만 커버링하는 방법이 있다. 만약 이후 7번, 3번, 8번 등 모든 구역을 계속해서 이 방법으로 커버링하면 기존의 방문 순서를 유지해도 될 것이다.
두 번째 커버링 방법
두 번째, 열 방향으로 커버링하는 방법이 있다. 2번 구역을 이렇게 커버링하고 나면 그 다음엔 7번 구역을 방문할 수 없다. 잘 생각해보면 이 문제에서 최소 커버링 횟수란 최소 DFS 깊이와도 같은데, 2번 구역을 방문한 후 7번 구역을 방문하게 되면 이미 커버링된 구역을 다시 커버링함으로써 의도한 대로 로직이 작동하지 않을 수 있다.
그러므로 2번 구역을 위와 같이 커버링한 이후엔 바로 오른쪽 구역인 3번 구역을 방문하게 될 것이다. 그리고 이 커버링 방식은 0행에서만 사용할 수 있다. 방문 순서가 column-major order이기 때문에 1행의 구역에서 이 커버링 방식을 사용하면 이전에 커버링된 구역을 침범하게 되어 이전의 상태와 현재의 상태가 충돌한다.
앞 문단이 이해가 잘 되지 않는다면 7번 구역에 방문했을 때를 생각해 보자. 2번 구역은 지금 살펴보고 있는 세 가지 커버링 방식 중 하나를 선택한 상황이다. 이 상태에서 7번 구역은 2번 구역을 포함해 커버링할 수 있을까?
세 번째 커버링 방법
세 번째, 행 방향으로 커버링하는 방법이 있다. 세 가지 커버링 방식 중 다음에 방문할 구역을 결정하기가 가장 까다로우며, 이 방식으로 인해 DFS에 매개변수가 하나 추가된다.
Case 1. 1행의 구역에 방문했고 이전 구역에서 세 번째 커버링 방법을 사용했다.
예를 들어 2번 구역에서 위와 같은 커버링 방식을 사용하고 7번 구역을 방문했다고 하자. 7번 구역에서 커버링을 수행한 후에 방문할 구역은 어디가 될까?
먼저 7번 구역에서 첫 번째 커버링 방법을 사용한 경우이다. 이때 3번 구역은 이미 커버링되었기 때문에 다음에는 8번 구역을 방문해야 한다.
다음으로 7번 구역에서 세 번째 커버링 방법을 사용한 경우이다. 이때 3번, 8번 구역은 이미 커버링되었기 때문에 다음에는 4번 구역을 방문해야 한다.
Case 2. 0행의 구역에 방문했고 이전 구역에서 세 번째 커버링 방법을 사용했다.
추가적인 예로 2번 구역에 방문했을 때 6번 구역에서 위와 같은 커버링 방식을 사용했다고 하자.
2번 구역에서 첫 번째 커버링 방식을 사용하면 다음에는 3번 구역을 방문해야 한다.
2번 구역에서 세 번째 커버링 방식을 사용하면 다음에는 8번 구역을 방문해야 한다.
위 두 가지 예시를 통해 다음과 같은 성질을 발견할 수 있다.
- 이전의 구역에서 세 번째 커버링 방법을 사용한 경우 다음에 방문할 구역은 다음과 같은 규칙에 따라 결정된다.
- 현재 구역에서 첫 번째 커버링 방법을 사용하면 그 다음엔 오른쪽에 있는 구역을 방문한다.
- 현재 구역에서 세 번째 커버링 방법을 사용하면 그 다음엔 방문 순서대로 2번 건너뛴 후 있는 구역을 방문해야 한다.
- 다음에 방문할 구역 및 커버링 방식(2번 구역에서 두 번째 커버링 방식을 사용할 수 있는지 생각해보자)을 결정하기 위해선 현재 구역의 커버링 방법뿐만 아니라 이전 구역의 커버링 방법도 알고 있어야 한다. 그러므로 현재 구역의 상태를 결정하기 위해 이전 구역의 상태가 필요하고, 이는 DFS의 매개변수로 이전 구역의 커버링 방법을 사용해야 함을 의미한다.
그러므로, 기본적으로 다음과 같은 정보들이 DFS의 각 깊이(구역)에서의 매개변수(상태)를 구성함을 알 수 있다.
- 행 번호(가지)
- 열 번호(가지)
- 이전 방문 구역에서 선택된 커버링 방법(기본적으로 가지, 최적화를 통해 가지로 설정 가능)
1-2. Circular structure
DFS 방문 순서와 캐싱할 매개변수 집합은 잘 구성되었다. 그런데 이제까지는 정말 중요한 정보 하나를 생략하고 있었다. 바로 배열이 환형 구조(Circular structure)라는 것이다. 1번 구역과 5번 구역, 그리고 6번 구역과 10번 구역은 하나의 구역으로 커버링될 수 있다.
위와 같은 상황을 생각해 보자. 방문 순서에 따라 1번 구역은 이미 커버링되었다. 그런데 5번 구역은 1번 구역과 함께 커버링이 가능하고, 그렇게 해야만 문제의 해를 구할 수 있는 상황이다. 이런 상황을 어떻게 해결할 수 있을까?
일단 1번 구역과 6번 구역이 커버링되었는지를 힌트로 전달해야 할 것이다. 이것은 1번 구역과 6번 구역이 커버링되지 않을 수도 있음을 의미한다. 앞서 살펴본 바와 같이 방문한 구역은 반드시 커버링이 되어야 하기 때문에 이 경우엔 먼저 커버링을 수행한 후, 해당 구역이 커버링될 수 없도록 조치가 필요하다.
1번 구역과 6번 구역의 커버링 여부를 힌트로 전달하기 위해 나는 일단 배열의 길이를 1열 확장하여 1번 구역과 6번 구역의 데이터를 복사했다. 경우의 수는 다음의 네 가지가 있다.
- 어떤 행의 양 끝 구역 간에도 커버링이 발생하지 않는 경우
- 0번째 행의 양 끝 구역(1번, 5번) 간에만 커버링이 발생하는 경우
- 1번째 행의 양 끝 구역(6번, 10번) 간에만 커버링이 발생하는 경우
- 모든 행의 양 끝 구역(1번, 5번 및 6번, 10번) 간 커버링이 발생하는 경우
각각에 대해 위 배열을 어떻게 조작해야 하는지 생각해 보겠다.
Case 1. 어떤 행의 양 끝 구역 간에도 커버링이 발생하지 않는 경우
이는 위 두 가지의 커버링이 발생해선 안 됨을 의미한다. 우선 양 끝에 있는 1번, 6번 구역은 메모리 상의 서로 다른 공간임을 인지하자.
이 경우에는 배열에서 오른쪽 끝에 있는 1번, 6번 구역의 값을 5번, 10번 구역의 값과 합했을 때 를 무조건 초과하도록 설정해 주면 된다. 그러면 5번, 10번 구역해 방문했을 때 세 번째 커버링 방법은 결코 사용할 수 없다.
Case 2. 0번째 행의 양 끝 구역 간에만 커버링이 발생하는 경우
위와 같은 커버링이 반드시 발생해야 하는 경우이다.
이때는 배열을 위와 같이 수정한 후 6번 구역부터 방문하도록 한다. 그래도 나중에 5번 구역이 방문되는 것은 막을 수가 없는데, 이때 첫 번째 커버링 방식이 집계되지 않도록 현재 방문한 구역의 값을 와 대조하도록 세부 로직을 구성할 것이다. 5번 구역에 방문하더라도 두 번째, 세 번째 커버링 방식은 당연히 사용할 수 없다는 점을 명심하자.
Case 3. 1번째 행의 양 끝 구역 간에만 커버링이 발생하는 경우
위와 같은 커버링이 반드시 발생해야 하는 경우이다.
1번 구역 먼저 방문하고 Case 2에서 언급한 방식으로 6번, 10번 구역의 커버링을 집계하지 않으면 된다. 또는 1번 구역 방문 시 이전 구역(환형 구조이므로 10번 구역)에서 세 번째 커버링 방식을 사용했다고 알리면 6번 구역은 방문하지 않게 된다.
Case 4. 모든 행의 양 끝 구역 간 커버링이 발생하는 경우
위와 같은 커버링이 반드시 발생해야 하는 경우이다.
2번 구역 먼저 방문하고 Case 2에서 언급한 방식으로 5번, 10번 구역의 커버링을 집계하지 않으면 된다.
이제 DFS 로직에 대한 설계를 마쳤고, 이대로만 구현해도 Top-down DP 기법을 활용할 수 있다.
1-2. Additional Optimization - Dimension Reduction
앞서 설계한 로직에 커버링 패턴을 기존 가지에서 가지로 축소하는 추가적인 최적화를 적용해 보았다.
다시 두 번째 커버링 방법을 살펴보자. 굳이 2번 구역에서 두 번째 커버링 방식을 사용하고 7번 구역에 방문할 필요가 있을까? 만약 그렇게 한다면 이전 구역에서 두 번째 커버링 방식을 사용했는지 검사하기 위해 추가적인 코드를 작성해야 할 것이다.
대신 두 번째 커버링 방식을 사용한 경우 다음에 오른쪽의 구역을 방문하면서 이전 구역에서 첫 번째 커버링 방식을 사용했다고 속인다면 어떨까? 잘 생각해 보면 이것은 유효하다.
그러므로 DFS의 매개변수 중 이전 방문 구역에서 선택된 커버링 방법은 첫 번째 방식, 세 번째 방식의 가지로 축소할 수 있다. 이렇게 함으로써 캐시의 차원도 축소되었다.
2. Solution
import java.io.*;
import java.util.*;
public class Main {
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static StringTokenizer st;
static StringBuilder sb = new StringBuilder();
static final int INF = 100_001;
static int T, N, W, result;
static int[][] map;
static int[][][] cache;
public static void main(String[] args) throws IOException {
T = Integer.parseInt(br.readLine());
while (T-- > 0)
sb.append(solve()).append('\n');
System.out.println(sb);
}
public static int solve() throws IOException {
st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
W = Integer.parseInt(st.nextToken());
map = new int[2][N + 1];
cache = new int[2][2][N];
for (int i = 0; i < 2; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < N; j++)
map[i][j] = Integer.parseInt(st.nextToken());
map[0][N] = map[0][0]; map[1][N] = map[1][0];
}
result = Integer.MAX_VALUE;
int t00 = map[0][0], t10 = map[1][0], t0n = map[0][N - 1], t1n = map[1][N - 1];
if (map[0][0] + map[0][N - 1] <= W) {
cleanCache();
map[0][0] = map[0][N - 1] = map[0][N] = INF;
result = Math.min(result, 1 + DFS(1, 0, 0));
map[0][0] = map[0][N] = t00; map[0][N - 1] = t0n;
}
if (map[1][0] + map[1][N - 1] <= W) {
cleanCache();
map[1][0] = map[1][N - 1] = map[1][N] = INF;
result = Math.min(result, 1 + DFS(0, 0, 1));
map[1][0] = map[1][N] = t10; map[1][N - 1] = t1n;
}
if (map[0][0] + map[0][N - 1] <= W && map[1][0] + map[1][N - 1] <= W) {
cleanCache();
map[0][0] = map[0][N - 1] = map[0][N] = map[1][0] = map[1][N - 1] = map[1][N] = INF;
result = Math.min(result, 2 + DFS(0, 1, 0));
map[0][0] = map[0][N] = t00; map[1][0] = map[1][N] = t10; map[0][N - 1] = t0n; map[1][N - 1] = t1n;
}
cleanCache();
map[0][N] = map[1][N] = INF;
result = Math.min(result, DFS(0, 0, 0));
return result;
}
/**
* @param prev: represents the previous cell's pattern
* 0: only that cell
* 1: that cell and horizontally adjacent cell
*/
public static int DFS(int h, int w, int prev) {
if (w >= N)
return 0;
else if (cache[prev][h][w] != INF)
return cache[prev][h][w];
int nh = 1 - h, nw = h == 0 ? w : w + 1;
// select pattern 1
cache[prev][h][w] = Math.min(cache[prev][h][w], (map[h][w] <= W ? 1 : 0) + DFS(prev != 1 ? nh : h, prev != 1 ? nw : w + 1, 0));
// select pattern 2
if (prev != 1 && h == 0 && map[0][w] + map[1][w] <= W)
cache[prev][h][w] = Math.min(cache[prev][h][w], 1 + DFS(h, w + 1, 0));
// select pattern 3
if (map[h][w] + map[h][w + 1] <= W) {
if (prev == 1)
cache[prev][h][w] = Math.min(cache[prev][h][w], 1 + DFS(1 - h, h == 0 ? w + 1 : w + 2, 0));
else
cache[prev][h][w] = Math.min(cache[prev][h][w], 1 + DFS(1 - h, h == 0 ? w : w + 1, 1));
}
return cache[prev][h][w];
}
public static void cleanCache() {
for (int[][] matrix : cache)
for (int[] row : matrix)
Arrays.fill(row, INF);
}
}먼저 DFS 로직을 살펴보자.
public static int DFS(int h, int w, int prev) {
if (w >= N)
return 0;
else if (cache[prev][h][w] != INF)
return cache[prev][h][w];
int nh = 1 - h, nw = h == 0 ? w : w + 1;
// select pattern 1
cache[prev][h][w] = Math.min(cache[prev][h][w], (map[h][w] <= W ? 1 : 0) + DFS(prev != 1 ? nh : h, prev != 1 ? nw : w + 1, 0));
// select pattern 2
if (prev != 1 && h == 0 && map[0][w] + map[1][w] <= W)
cache[prev][h][w] = Math.min(cache[prev][h][w], 1 + DFS(h, w + 1, 0));
// select pattern 3
if (map[h][w] + map[h][w + 1] <= W) {
if (prev == 1)
cache[prev][h][w] = Math.min(cache[prev][h][w], 1 + DFS(1 - h, h == 0 ? w + 1 : w + 2, 0));
else
cache[prev][h][w] = Math.min(cache[prev][h][w], 1 + DFS(1 - h, h == 0 ? w : w + 1, 1));
}
return cache[prev][h][w];
}현재 방문 구역 및 이전 방문 구역에서 선택한 커버링 방법에 따라 다음 방문 구역이 어떻게 결정되는지, 그리고 다음 방문 구역엔 어떤 커버링 방법을 선택했다고 알리는지 잘 관찰해 보자.
result = Integer.MAX_VALUE;
int t00 = map[0][0], t10 = map[1][0], t0n = map[0][N - 1], t1n = map[1][N - 1];
if (map[0][0] + map[0][N - 1] <= W) {
cleanCache();
map[0][0] = map[0][N - 1] = map[0][N] = INF;
result = Math.min(result, 1 + DFS(1, 0, 0));
map[0][0] = map[0][N] = t00; map[0][N - 1] = t0n;
}
if (map[1][0] + map[1][N - 1] <= W) {
cleanCache();
map[1][0] = map[1][N - 1] = map[1][N] = INF;
result = Math.min(result, 1 + DFS(0, 0, 1));
map[1][0] = map[1][N] = t10; map[1][N - 1] = t1n;
}
if (map[0][0] + map[0][N - 1] <= W && map[1][0] + map[1][N - 1] <= W) {
cleanCache();
map[0][0] = map[0][N - 1] = map[0][N] = map[1][0] = map[1][N - 1] = map[1][N] = INF;
result = Math.min(result, 2 + DFS(0, 1, 0));
map[0][0] = map[0][N] = t00; map[1][0] = map[1][N] = t10; map[0][N - 1] = t0n; map[1][N - 1] = t1n;
}
cleanCache();
map[0][N] = map[1][N] = INF;
result = Math.min(result, DFS(0, 0, 0));코드가 좀 지저분하긴 하지만, 환형 구조의 양 끝에서 발생하는 커버링의 경우마다 캐시를 초기화하고 DFS를 다시 수행하도록 구성했다.
3. Conclusion
자력솔에 거의 근접했지만 아쉽게도 앞서 살펴본 예제에서 배열의 끝에 1번, 6번 구역을 복사하고 INF 값을 활용하는 논리는 Bottom-up DP를 활용한 풀이에서 영감을 얻었다.
작년에 처음 이 문제를 봤을 때는 '내가 이 문제를 풀이과정을 보고서라도 이해할 수 있을까?'하는 생각을 갖고 있었는데 이해한 후 풀이과정을 내 방식으로 서술할 수 있을 만큼 PS 실력이 개선된 것 같아 뿌듯하다.
Top-down DP 기법은 DFS 알고리즘을 기반으로 하여 적용되는 것이기 때문에 이 문제와 같이 다수의 조건 분기로 사용자에 의해 서로 다른 조건의 DFS 호출이 여러 번 발생하는 상황을 금방 납득할 수 있었다. DP 태그의 문제는 난해해질수록 Top-down DP 기법이 빛을 발하게 되는 듯하다.
