문제 링크
크기의 직사각형 종이가 주어지고 종이는 크기의 정사각형으로 이루어져 있다.
각 정사각형엔 수가 적혀있고 테트로미노 도형으로 정사각형들을 가릴 때 가려진 정사각형에 적힌 수들의 합의 최대값을 구하는 문제이다.
첫 번째 접근 방법은 이러했다.
각 테트로미노는 4개의 정사각형으로 이루어져 있고 연결되어 있으니 DFS로 각 시작 지점에서 크기가 4인 모양을 탐색하면 될 거라 생각했다.
이렇게 구현해놓고 보니 테트로미노 중 'ㅗ' 모양을 탐색할 수 없는 문제점이 발생했다.
그래서 ㅗ모양은 따로 다시 구현해서 해결해주었다.
추가로 중복해서 탐색하는 부분이 많다는 걸 인지하고 있었는데 시간 제한이 크게 부족하진 않아서dx[], dy[]부분에서 상하좌우로 이동할 수 있던 걸 상하우(좌를 뺌)로만 이동하게 해서 중복 부분을 조금 줄였는데 시간에 큰 영향은 못끼친 듯 하다.
220627 수정
코드를 새로 짜면서 중복 탐색 부분은 최적화는 하지 않았습니다.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int n, m;
int ans = 0;
int board[500][500];
const int dx[] = {1, 0, 0};
const int dy[] = {0, 1, -1};
bool visited[500][500];
const int a[4][4] = {
{0, 1, 1, 2}, {0, 1, 1, 2}, {0, 0, 0, 1}, {0, 0, 0, -1}
};
const int b[4][4] = {
{0, 0, 1, 0}, {0, 0, -1, 0}, {0, 1, 2, 1}, {0, 1, 2, 1}
};
bool InRange(int y, int x) {
return (0 <= y && y < n && 0 <= x && x < m);
}
void Dfs(int y, int x, int n, int sum) {
visited[y][x] = true;
sum += board[y][x];
n++;
if (n == 4) {
ans = max(ans, sum);
visited[y][x] = false;
return;
}
for (int i = 0; i < 3; ++i) {
int ny = y + dy[i], nx = x + dx[i];
if (!InRange(ny, nx)) continue;
if (visited[ny][nx]) continue;
Dfs(ny, nx, n, sum);
}
visited[y][x] = false;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> n >> m;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
cin >> board[i][j];
}
}
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
Dfs(i, j, 0, 0);
}
}
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
for (int k = 0; k < 4; ++k) {
bool flag = true;
int s = 0;
for (int l = 0; l < 4; ++l) {
if (!InRange(i + a[k][l], j + b[k][l])) {
flag = false;
break;
}
s += board[i + a[k][l]][j + b[k][l]];
}
if (flag) ans = max(ans, s);
}
}
}
cout << ans << '\n';
}
코드를 다시 짜면서 느낀 점이지만 가독성 좋게 코드 짜는 게 참 어려운 일인거 같다. 변수명도 최대한 자세히 쓰려 했는데 기존 코드보다 조금 나아진 거에 만족해야겠다... 다음엔 더 좋은 코드를 짤 수 있겠지
와, 전 못풀었는데... 대단쓰