[알고리즘] 테트로미노

• 포인트
• 문제의 요점은 전부를 채우는 것이 아니라 하나를 놔서 제일 높은 점수를 구하는 것이다.
• ㅗ, ㅏ, ㅜ, ㅓ 의 모양을 제외하고는 전부 dfs로 다음 값을 찾을 수 있다.  
• 19가지 모양으로 나누어서 이를 적용해서 풀이할 수 있다.

🧶문서는 항상 수정 될 수 있습니다. 비판은 환영합니다. 

c++/cpp

#include<iostream>
#include<cstring>

#define MAX 500
using namespace std;

int n, m, answer;
int map[MAX][MAX];
bool visited[MAX][MAX];

int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};

void go(int x, int y, int sum, int cnt) {
    visited[x][y] = true;
    if (cnt == 3) {
        answer = max(answer, sum);
        return;
    }

    for (int i = 0; i < 4; i++) {
        int nx = x + dx[i];
        int ny = y + dy[i];

        if (nx < 0 || ny < 0 || nx >= n || ny >= m) continue;
        if (!visited[nx][ny]) {
            go(nx, ny, sum + map[nx][ny], cnt + 1);
            visited[nx][ny] = false;
        }
    }
}

void shape1(int x, int y) {
    int sum;
    sum = map[x][y] + map[x][y + 1] + map[x][y + 2] + map[x - 1][y + 1];
    answer = max(answer, sum);
}

void shape2(int x, int y) {
    int sum;
    sum = map[x][y] + map[x][y + 1] + map[x][y + 2] + map[x + 1][y + 1];
    answer = max(answer, sum);
}

void shape3(int x, int y) {
    int sum;
    sum = map[x][y] + map[x + 1][y] + map[x + 2][y] + map[x + 1][y + 1];
    answer = max(answer, sum);
}

void shape4(int x, int y) {
    int sum;
    sum = map[x][y] + map[x - 1][y + 1] + map[x][y + 1] + map[x + 1][y + 1];
    answer = max(answer, sum);
}


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++) {
            memset(visited, false, sizeof(visited));
            go(i, j, map[i][j], 0);
            if (i - 1 >= 0 && j + 2 < m) shape1(i, j);
            if (j + 2 < m && i + 1 < n) shape2(i, j);
            if (i + 2 < n && j + 1 < m) shape3(i, j);
            if (i + 1 < n && i - 1 >= 0 && j + 1 < m) shape4(i, j);
        }
    }

    cout << answer << endl;

    return 0;
}

 

python

import sys

sys.stdin = open('input.txt')
input = sys.stdin.readline


def find(x: int, y: int) -> None:
	global answer
	for i in range(19):
		result = 0
		for j in range(4):
			nx, ny = x + tetromino[i][j][0], y + tetromino[i][j][1]
			if not (0 <= nx < n and 0 <= ny < m):
				continue
			result += data[nx][ny]
		answer = max(answer, result)


tetromino = [
	[(0, 0), (0, 1), (1, 0), (1, 1)],  # ㅁ
	[(0, 0), (0, 1), (0, 2), (0, 3)],  # ㅡ
	[(0, 0), (1, 0), (2, 0), (3, 0)],  # ㅣ
	[(0, 0), (0, 1), (0, 2), (1, 0)],
	[(1, 0), (1, 1), (1, 2), (0, 2)],
	[(0, 0), (1, 0), (1, 1), (1, 2)],
	[(0, 0), (0, 1), (0, 2), (1, 2)],  # ㄴ
	[(0, 0), (1, 0), (2, 0), (2, 1)],
	[(2, 0), (2, 1), (1, 1), (0, 1)],
	[(0, 0), (0, 1), (1, 0), (2, 0)],
	[(0, 0), (0, 1), (1, 1), (2, 1)],  # ㄱ
	[(0, 0), (0, 1), (0, 2), (1, 1)],  # ㅜ
	[(1, 0), (1, 1), (1, 2), (0, 1)],  # ㅗ
	[(0, 0), (1, 0), (2, 0), (1, 1)],  # ㅏ
	[(1, 0), (0, 1), (1, 1), (2, 1)],  # ㅓ
	[(1, 0), (2, 0), (0, 1), (1, 1)],
	[(0, 0), (1, 0), (1, 1), (2, 1)],
	[(1, 0), (0, 1), (1, 1), (0, 2)],
	[(0, 0), (0, 1), (1, 1), (1, 2)]
]

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

answer = 0
for i in range(n):
	for j in range(m):
		find(i, j)

print(answer)