[백준] 14500 테트로미노

14500번: 테트로미노

 

www.acmicpc.net

풀이

완전탐색으로 해결할 수 있는 문제이다. 폴리오미노를 잘 살펴보면 ㅜ 모양을 제외하고서는 한붓그리기로 그릴 수 있는 모양이다. 즉 DFS를 통해 탐색할 수 있는 모양이다. 따라서 백트래킹으로 사용해서 모든 경우를 다 확인하고, 확인하지 못한 ㅜ모양만 따로 확인해주면 쉽게 해결할 수 있다.

코드

#include <iostream>
#include <algorithm>
using namespace std;

int n, m, ans;
int map[500][500];
bool visited[500][500];
const int dx[] = { -1, 0, 1, 0 }, dy[] = { 0, -1, 0, 1 };

void dfs(int x, int y, int cnt, int sum) {
    if (cnt == 4) {
        ans = max(ans, sum);
        return;
    }

    for (int i = 0; i < 4; i++) {
        int nx = x + dx[i];
        int ny = y + dy[i];
        if (nx < 0 || nx > m - 1 || ny < 0 || ny > n - 1) continue;
        if (!visited[ny][nx]) {
            visited[ny][nx] = true;
            dfs(nx, ny, cnt + 1, sum + map[ny][nx]);
            visited[ny][nx] = false;
        }
    }
}

// ㅜ 모양 블럭
void calculate_edge_case(int x, int y) {
    // ㅗ
    if (1 <= x && x <= m - 2 && 1 <= y && y <= n - 1) ans = max(ans, map[y][x - 1] + map[y][x] + map[y][x + 1] + map[y - 1][x]);
    // ㅓ
    if (1 <= x && x <= m - 1 && 1 <= y && y <= n - 2) ans = max(ans, map[y][x - 1] + map[y][x] + map[y + 1][x] + map[y - 1][x]);
    // ㅜ
    if (1 <= x && x <= m - 1 && 0 <= y && y <= n - 2) ans = max(ans, map[y][x - 1] + map[y][x] + map[y][x + 1] + map[y + 1][x]);
    // ㅏ
    if (0 <= x && x <= m - 2 && 1 <= y && y <= n - 2) ans = max(ans, map[y][x + 1] + map[y][x] + map[y + 1][x] + map[y - 1][x]);
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    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++) {
            visited[i][j] = true;
            dfs(j, i, 1, map[i][j]);
            visited[i][j] = false;
            calculate_edge_case(j, i);
        }
    }
    cout << ans << '\n';
    return 0;
}