문제: BOJ 14500 — 테트로미노 · English · 日本語
N × M 크기의 보드에서 변을 공유하며 연결된 네 칸을 덮는 테트로미노를 놓을 때, 덮인 칸의 합 중 최댓값을 구합니다. 다섯 가지 테트로미노의 모든 회전과 대칭 배치를 고려해야 합니다.
인접한 칸을 하나씩 추가하며 단순 경로를 깊이 우선 탐색하면 막대, L, S, Z 모양은 찾을 수 있지만 T 모양은 만들 수 없습니다. T 모양의 세 갈래 접점에서는 한 경로만 따라가는 대신 가지가 필요하기 때문입니다. 따라서 길이 4인 모든 단순 경로를 탐색하고, 각 칸을 중심으로 하는 T 모양 네 방향을 별도로 검사합니다. 칸을 읽기 전에 보드 범위를 확인하므로 폭이 얇은 보드와 가장자리 배치도 안전하게 처리됩니다.
각 칸에서 깊이가 4인 탐색의 분기 수는 상수이며, T 방향도 네 개뿐이므로 전체 시간 복잡도는 모양 개수에 따른 상수를 포함한 O(NM)입니다. 칸의 값과 합은 long long으로 다뤄 합산 중 오버플로를 방지합니다.
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
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
int n, m;
vector<vector<long long>> board;
vector<vector<bool>> visited;
long long answer = 0;
const int dr[4] = {-1, 1, 0, 0};
const int dc[4] = {0, 0, -1, 1};
void dfs(int r, int c, int count, long long sum) {
if (count == 4) {
answer = max(answer, sum);
return;
}
for (int d = 0; d < 4; ++d) {
int nr = r + dr[d];
int nc = c + dc[d];
if (nr < 0 || nr >= n || nc < 0 || nc >= m || visited[nr][nc]) continue;
visited[nr][nc] = true;
dfs(nr, nc, count + 1, sum + board[nr][nc]);
visited[nr][nc] = false;
}
}
void checkT(int r, int c) {
const int shapes[4][3][2] = {
{{0, -1}, {0, 1}, {-1, 0}},
{{0, -1}, {0, 1}, {1, 0}},
{{-1, 0}, {1, 0}, {0, -1}},
{{-1, 0}, {1, 0}, {0, 1}}
};
for (const auto& shape : shapes) {
long long sum = board[r][c];
bool valid = true;
for (const auto& offset : shape) {
int nr = r + offset[0];
int nc = c + offset[1];
if (nr < 0 || nr >= n || nc < 0 || nc >= m) {
valid = false;
break;
}
sum += board[nr][nc];
}
if (valid) answer = max(answer, sum);
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> m;
board.assign(n, vector<long long>(m));
visited.assign(n, vector<bool>(m, false));
for (int r = 0; r < n; ++r) {
for (int c = 0; c < m; ++c) cin >> board[r][c];
}
for (int r = 0; r < n; ++r) {
for (int c = 0; c < m; ++c) {
visited[r][c] = true;
dfs(r, c, 1, board[r][c]);
visited[r][c] = false;
checkT(r, c);
}
}
cout << answer << '\n';
return 0;
}