백준[14500] - 테트로미노

문제

백준 14500 문제 보기

접근 방법

각 좌표에서 모든 방향에 대해 dfs 탐색을 진행하면 테트리스의 모양 대로 접근할 수 있다. 하지만 모양은 dfs로는 접근할 수 없는 모양이므로 따로 예외처리를 해주어야 한다.

코드

#include <iostream>
#include <algorithm>
using namespace std;
int dr[4] = {1, 0, -1, 0};
int dc[4] = {0, 1, 0, -1};
int map[501][501];
int chk[501][501];
int N, M, ans = 0;
void check() {
// ㅗ
for(int i = 1; i < N; i ++) {
for(int j = 1; j < M - 1; j ++) {
int temp = map[i][j] + map[i - 1][j] + map[i][j - 1] + map[i][j + 1];
ans = max(ans, temp);
}
}
// ㅜ
for(int i = 0; i < N - 1; i ++) {
for(int j = 1; j < M - 1; j ++) {
int temp = map[i][j] + map[i + 1][j] + map[i][j - 1] + map[i][j + 1];
ans = max(ans, temp);
}
}
// ㅓ
for(int i = 1; i < N - 1; i ++) {
for(int j = 1; j < M; j ++) {
int temp = map[i][j] + map[i + 1][j] + map[i - 1][j] + map[i][j - 1];
ans = max(ans, temp);
}
}
// ㅏ
for(int i = 1; i < N - 1; i ++) {
for(int j = 0; j < M - 1; j ++) {
int temp = map[i][j] + map[i + 1][j] + map[i - 1][j] + map[i][j + 1];
ans = max(ans, temp);
}
}
}
void dfs(int r, int c, int cnt, int sum) {
if(cnt == 4) {
ans = max(ans, sum);
return;
}
for(int i = 0; i < 4; i ++) {
int nextR = r + dr[i];
int nextC = c + dc[i];
if (nextR < N && nextR >= 0 && nextC < M && nextC >= 0 && chk[nextR][nextC] != 1) {
chk[nextR][nextC] = 1;
dfs(nextR, nextC, cnt + 1, sum + map[nextR][nextC]);
chk[nextR][nextC] = 0;
}
}
}
int main() {
cin >> N >> M;
for(int i = 0; i < N; i ++) {
for(int j = 0; j < M; j ++) {
cin >> map[i][j];
}
}
for(int i = 0; i < N; i ++) {
for(int j = 0; j < M; j ++) {
chk[i][j] = 1;
dfs(i, j, 1, map[i][j]);
chk[i][j] = 0;
}
}
check();
cout << ans;
return 0;
}
Share