[Algorithm] cpp 백준 1144번: 싼 비용

문제

링크: https://www.acmicpc.net/problem/1144
요약: N×M 격자의 각 칸에 정수 비용이 주어질 때, 상하좌우로 연결된 칸들로 이루어진 하나의 집합을 골라 그 비용 합의 최솟값을 구한다. 크기 0의 집합(공집합)도 허용된다.
제한/스펙: N, M ≤ 9, 각 칸의 비용 |value| ≤ 1000, 시간 제한 2초

입력/출력

1
2
3
4
5
6
7
8
입력
N M
v[0][0] v[0][1] ... v[0][M-1]
...
v[N-1][0] ...     v[N-1][M-1]

출력
가장 싼 연결된 칸 집합의 비용 합(정수)

예시

접근 개요

핵심 관찰: 행 우선(좌→우, 위→아래)으로 스캔할 때, “현재 칸 위쪽에서 내려오는 연결 라벨들과 왼쪽 인접 라벨"만이 연결성 판단에 필요하다.
상태 정의(프로파일): cur는 최근 M칸(현재 칸의 바로 위 열까지)의 연결 컴포넌트 라벨을 문자로 저장. 같은 라벨은 같은 컴포넌트를 의미. 매 스텝마다 라벨을 정규화(normalize)하여 동치 상태를 하나로 압축.
전이:
- 미선택(skip): 현재 칸을 고르지 않음. 위에서 내려오는 열의 컴포넌트가 고립되지 않았을 때만 허용(checkPass).
- 선택(take): 현재 칸을 고름. 위(up) 라벨과 좌(left) 라벨을 병합해 새 라벨 구성(merge).
종료/유효성: 모든 칸을 처리한 뒤, 프로파일에 남아있는 개방 컴포넌트 수가 0 또는 1일 때만 유효(checkValid). 빈 집합 허용이므로 언제든 0과 비교해 최소 갱신.

알고리즘 설계

상태: DP(x, y, cur) = (x, y)부터 끝까지 처리할 때 만들 수 있는 단일 연결 컴포넌트의 최소 비용 합.
정규화: 프로파일 문자를 좌측부터 1,2,3,…로 재라벨링해 동치 상태를 하나로 만듦 → 메모리·시간 절약.
고립 방지(checkPass): 현재 칸을 건너뛰면 up 라벨이 좌측의 어떤 라벨과도 이어지지 않으면 위쪽이 고립됨. 이를 막아 연결성 보장.
병합(merge): 선택 시 위/좌 라벨을 규칙대로 병합. 모두 0이면 새 라벨 생성, 하나만 0이면 그 하나 사용, 둘 다 있고 다르면 전체 프로파일에서 둘을 하나로 통합.
정당성 스케치: (1) 프로파일은 향후 연결성에 영향을 미치는 충분한 정보(필요조건)를 보존한다. (2) 정규화로 동치 상태를 한 상태로 모아 최적 부분구조를 유지한다. (3) checkPass/Valid로 위쪽 고립과 다중 컴포넌트 종료를 배제해 전역적으로 하나의 컴포넌트만 형성되도록 한다.

복잡도

상태 수는 M ≤ 9에서 가능한 연결 라벨링의 개수 T에 비례(카탈란 유사 규모). 전체 복잡도는 대략 O(N·M·T). 실측상 N,M ≤ 9에서 충분히 2초 내 동작.

구현 (C++)

 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
// 더 많은 정보는 42jerrykim.github.io 에서 확인하세요.
#include <bits/stdc++.h>
using namespace std;

static const int INF = 1e9;

int n, m;
int grid[9][9];
vector<vector<unordered_map<string, int>>> memo;

static inline string normalizeProfile(const string& s) {
	string normalized(s.size(), '0');
	unsigned char remap[256] = {0};
	char nextLabel = '1';
	for (size_t i = 0; i < s.size(); ++i) {
		char c = s[i];
		if (c == '0') continue;
		if (!remap[(unsigned char)c]) remap[(unsigned char)c] = nextLabel++;
		normalized[i] = remap[(unsigned char)c];
	}
	return normalized;
}

static inline bool checkPass(const string& s) {
	if (s[0] == '0') return true;
	for (size_t i = 1; i < s.size(); ++i) if (s[i] == s[0]) return true;
	return false;
}

static inline bool checkValid(const string& s) {
	bool seen[256] = {false};
	int cnt = 0;
	for (char c : s) if (c != '0' && !seen[(unsigned char)c]) {
		seen[(unsigned char)c] = true;
		if (++cnt > 1) return false;
	}
	return true;
}

static inline string mergeWithLeft(const string& s) {
	string ret = s;
	char up = s[0];
	char left = s.back();
	ret.erase(ret.begin());
	if (up == '0' && left == '0') ret.push_back('9');
	else if (up == '0') ret.push_back(left);
	else if (left == '0' || up == left) ret.push_back(up);
	else {
		for (char& c : ret) if (c == left) c = up;
		ret.push_back(up);
	}
	return normalizeProfile(ret);
}

static inline string mergeNoLeft(const string& s) {
	string ret = s; ret.erase(ret.begin());
	char up = s[0];
	ret.push_back(up == '0' ? '9' : up);
	return normalizeProfile(ret);
}

int dfs(int x, int y, string cur) {
	if (x == n) return checkValid(cur) ? 0 : INF;
	cur = normalizeProfile(cur);
	auto& cache = memo[x][y];
	if (auto it = cache.find(cur); it != cache.end()) return it->second;
	int best = INF;
	int nx = x, ny = y + 1; if (ny >= m) { nx++; ny = 0; }
	if (checkPass(cur)) {
		string nxt = cur; nxt.erase(nxt.begin()); nxt.push_back('0');
		best = min(best, dfs(nx, ny, nxt));
	}
	string nxtTake = (y ? mergeWithLeft(cur) : mergeNoLeft(cur));
	best = min(best, dfs(nx, ny, nxtTake) + grid[x][y]);
	if (checkValid(cur)) best = min(best, 0);
	return cache[cur] = best;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cin >> n >> m;
	for (int i = 0; i < n; ++i) for (int j = 0; j < m; ++j) cin >> grid[i][j];
	memo.assign(n, vector<unordered_map<string, int>>(m));
	cout << dfs(0, 0, string(m, '0')) << '\n';
	return 0;
}

구현 (Python)

 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
# 더 많은 정보는 42jerrykim.github.io 에서 확인하세요.
import sys
sys.setrecursionlimit(1_000_000)
input = sys.stdin.readline

INF = 10**9

n, m = map(int, input().split())
grid = [list(map(int, input().split())) for _ in range(n)]

from functools import lru_cache

def normalize_profile(s: str) -> str:
    remap = {}
    next_label = ord('1')
    out = []
    for ch in s:
        if ch == '0':
            out.append('0')
        else:
            if ch not in remap:
                remap[ch] = chr(next_label)
                next_label += 1
            out.append(remap[ch])
    return ''.join(out)

def check_pass(s: str) -> bool:
    if s[0] == '0':
        return True
    for i in range(1, len(s)):
        if s[i] == s[0]:
            return True
    return False

def check_valid(s: str) -> bool:
    seen = set()
    for ch in s:
        if ch != '0':
            seen.add(ch)
            if len(seen) > 1:
                return False
    return True

def merge_with_left(s: str) -> str:
    up = s[0]
    left = s[-1]
    ret = s[1:]
    if up == '0' and left == '0':
        ret += '9'
    elif up == '0':
        ret += left
    elif left == '0' or up == left:
        ret += up
    else:
        # replace all left with up
        table = str.maketrans({left: up})
        ret = ret.translate(table) + up
    return normalize_profile(ret)

def merge_no_left(s: str) -> str:
    up = s[0]
    ret = s[1:] + ('9' if up == '0' else up)
    return normalize_profile(ret)

@lru_cache(maxsize=None)
def dfs(x: int, y: int, cur: str) -> int:
    if x == n:
        return 0 if check_valid(cur) else INF
    cur = normalize_profile(cur)
    nx, ny = x, y + 1
    if ny >= m:
        nx += 1
        ny = 0
    best = INF
    if check_pass(cur):
        nxt = cur[1:] + '0'
        best = min(best, dfs(nx, ny, nxt))
    nxt_take = merge_with_left(cur) if y > 0 else merge_no_left(cur)
    best = min(best, dfs(nx, ny, nxt_take) + grid[x][y])
    if check_valid(cur):
        best = min(best, 0)
    return best

print(dfs(0, 0, '0' * m))