백준10937 두부 모판 자르기

작성일 | In

문제 링크

  • http://icpc.me/10937

문제 출처

  • 2006 KOI 전국 본선 고등2

사용 알고리즘

  • DP
  • BitMask

시간복잡도

  • O(n22n)

풀이

대부분의 글에서 이 문제를 MCMF를 활용해 해결하는 방법을 설명하고 있습니다. 저는 MCMF가 아닌 Bit DP를 활용해서 설명을 하도록 하겠습니다.

먼저, 두부의 등급에 대한 가치를 배열에 미리 저장해두고 시작합시다. 모판도 함께 미리 정의해둡시다.

1
2
3
4
5
6
7
int cost[4][4] = {
	{100, 70, 40, 0},
	{70, 50, 30, 0},
	{40, 30, 20, 0},
	{0, 0, 0, 0}
};
int board[11][11]; //zero-based
Naive 풀이

백트래킹을 이용한 Naive풀이를 먼저 생각해봅시다.
n*n크기의 전체 모판을 행 우선탐색을 할 것입니다.

현재 위치 (i, j)에 대해 할 수 있는 동작은 3가지입니다.

  1. (i, j) + (i+1, j) 판매하기
  2. (i, j) + (i, j+1) 판매하기
  3. 현재 위치의 두부를 판매하지 않기

행 우선으로 탐색을 하기 때문에, i가 n이 되면 모든 행을 다 탐색한 것을 의미하므로 탐색을 종료하면 됩니다. 그러나 j가 n이라면 현재 행을 다 탐색한 것이므로 다음 행 0번 열로 넘어가면 됩니다.

간단하게 재귀함수로 구현해봅시다. 함수를 구현하기 전에, 판매여부를 저장할 chk라는 배열을 미리 만들어둡시다.

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
int chk[11][11];
int f(int i, int j){
  int ans = 0;
  if(i == n) return 0; //탐색 종료
  if(j == n) return f(i+1, 0); //다음 행

  if(!chk[i][j]){ //현재 위치 판매x
    chk[i][j] = 1;
    if(j+1 < n && !chk[i][j+1]){ //가로
      int now = board[i][j], nxt = board[i][j+1];
      chk[i][j+1] = 1;
      ans = max(ans, f(i, j+2) + cost[now][nxt]);
      chk[i][j+1] = 0;
    }
    if(i+1 < n && !chk[i+1][j]){ //세로
      int now = board[i][j], nxt = board[i+1][j];
      chk[i+1][j] = 1;
      ans = max(ans, f(i, j+1) + cost[now][nxt]);
      chk[i+1][j] = 0;
    }
    ans = max(ans, f(i, j+1)); //구매 x
  }
  else ans = max(ans, f(i, j+1)); //다음 위치
  return ans;
}

이 코드는 대략 O(3(n2))정도의 시간이 걸리는, 아주 비효율적인 풀이입니다. 최악의 경우에는 O(3121)이 걸립니다.

Bit DP

사진을 하나 봅시다.

현재 위치가 (2, 2)라면, 행 우선 탐색을 하기 때문에 (0, 0) ~ (2, 1)까지는 모두 두부를 살지, 안살지 결정을 한 상태입니다. 그리고 (3, 3)부터 (6, 6)까지는 탐색을 하지 않은 상태입니다.
그러나 (2, 2)부터 (3, 2)까지 총 8개의 두부는 구매 여부가 결정되지 않았습니다.

이렇게 각각의 순간마다 구매 여부가 결정되지 않은 곳은 최대 n+1개가 생깁니다. n+1개의 구매 여부를 각각 하나의 비트로 나타내면 2n+1개의 경우의 수가 나오게 되고, 최대 4096가지의 경우의 수가 나옵니다.
현재 위치와 n+1개의 상태를 기준으로 메모이제이션을 한다면 O(n22n)만에 답을 구할 수 있습니다.


현재 위치를 2n, 오른쪽 위치를 2n-1, 현재 위치의 바로 아래 칸을 1에 해당하는 bit로 나타냅시다.
현재 위치에서 고려해야 할 곳은 나 자신과 오른쪽, 바로 아래 총 3가지 뿐입니다. 상수를 선언해줍시다.
CUR = (1 << n), RIGHT = (1 << (n-1)), DOWN = 1
한 칸 오른쪽으로 이동할 때마다 bit를 오른쪽으로 shift해줍니다. 밖으로 나간 bit를 없애기 위해 상수를 하나 더 정의합시다.
MOD = (1 << (n+1))

위에서 정의한 4가지 상수와 메모이제이션을 이용해 탐색 코드를 다시 구현해봅시다.

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
int dp[11][11][1 << 12];
memset(dp, -1, sizeof(dp));

int f(int i, int j, int bit){
  int &ret = dp[i][j][bit];
  if(ret != -1) return ret; //이미 탐색 완료
  if(i == n) return ret = 0;
  if(j == n) return ret = f(i+1, 0, bit);

  if(!(bit & CUR)){ //현재 위치 포함 x
    if(j+1 < n && !(bit & RIGHT)){
      int now = board[i][j], nxt = board[i][j+1];
      int t1 = f(i, j+1, (bit<<2) % MOD) + cost[now][nxt];
      ret = max(ret, t1);
    }
    if(i+1 < n && !(bit&DOWN)){
      int now = board[i][j], nxt = board[i+1][j];
      int t2 = f(i, j+1, ((bit|DOWN)<<1) % MOD) + cost[now][nxt];
      ret = max(ret, t2);
    }
    int t3 = f(i, j+1, (bit<<1) % MOD);
    ret = max(ret, t3);
  }
  int t4 = f(i, j+1, (bit<<1) % MOD);
  ret = max(ret, t4);

  return ret;
}

아래는 전체 코드입니다.

전체 코드

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
#include <bits/stdc++.h>
using namespace std;

int cost[4][4] = {
	{100, 70, 40, 0},
	{70, 50, 30, 0},
	{40, 30, 20, 0},
	{0, 0, 0, 0}
};
int dp[11][11][1 << 12];
int board[11][11];
int n;

int CUR, RIGHT, DOWN, MOD;

int f(int i, int j, int bit){
	int &ret = dp[i][j][bit];
	if(ret != -1) return ret;
	if(i == n) return ret = 0;
	if(j == n) return ret = f(i+1, 0, bit);

	if(ret == -1){
		if(!(bit & CUR)){ //현재 선택 안했다면
			if(j+1 < n && !(bit&RIGHT)){ //오른쪽
				int now = board[i][j];
				int nxt = board[i][j+1];
				int t1 = f(i, j+2, (bit<<2) % MOD) + cost[now][nxt];
				ret = max(ret, t1);
			}
			if(i+1 < n && !(bit&DOWN)){ //오른쪽
				int now = board[i][j];
				int nxt = board[i+1][j];
				int t2 = f(i, j+1, ((bit|DOWN)<<1) % MOD) + cost[now][nxt];
				ret = max(ret, t2);
			}
			int t3 = f(i, j+1, (bit<<1) % MOD);
			ret = max(ret, t3);
		}
		int t4 = f(i, j+1, (bit<<1) % MOD);
		ret = max(ret, t4);
	}
	return ret;
}

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin >> n;
	CUR = (1 << n), RIGHT = (1 << (n-1)), DOWN = 1, MOD = (1 << (n+1));

	for(int i=0; i<n; i++){
		for(int j=0; j<n; j++){
			char t; cin >> t;
			board[i][j] = t=='F' ? 3 : t-'A';
		}
	}

	memset(dp, -1, sizeof(dp));
	cout << f(0, 0, 0);
}