백준 14500 테트로미노 (파이썬)

https://www.acmicpc.net/problem/14500

14500번: 테트로미노

가로2칸, 세로2칸을 지정한 후 두번째 칸부터 dfs로 이동한다

 

■■ ■■■

■□ ■

■□

예외1. 위 2가지 경우를 포함하지 않기 때문에 따로 처리한다

예외2. ㅗ 모양을 회전하는 경우 4가지도 따로 처리한다

 

1. 가로 2칸씩 이동하는 반복문과 세로 2칸씩 이동하는 반복문 2개를 만든다

2. _sum 변수에 2칸의 값을 저장한다

3. 앞서 말한 예외 케이스 2가지를 조건문으로 먼저 구한다

   가로 두칸일 경우

   ■■ ■□ □■

   ■□ ■■ ■■

   ■□ ■□ □■

   위 3 가지 케이스를 구하게 되고 세로 두칸일 경우는 나머지 케이스를 구하게 된다

4. dfs에서 이동을 체크할 리스트 c를 만든다

   이 때 주어진 지도의 범위가 크기 때문에 가로의 경우 5x4, 세로는 4x5 사이즈로 만든다

   가로의 경우 c[2][0]부터, 세로의 경우 c[0][2]부터 시작하면 모든 도형을 만들 수 있다

5. dfs 함수는 좌표와 이동한 횟수, 각 칸의 합, 리스트 c의 좌표를 입력받는다

   좌표값을 옮길 때 c의 좌표값도 같이 옮겨서 같은 방향으로 움직이게 만든다

6. dfs로 이동하면서 cnt가 3이면 4칸을 모두 정한 것이기 때문에 최대값을 갱신한다

import sys

input = sys.stdin.readline
dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]

def check(x, y, cnt, _sum, cx, cy):
    global ans
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        ncx = cx + dx[i]
        ncy = cy + dy[i]
        if not 0 <= nx < n or not 0 <= ny < m or c[ncx][ncy]:
            continue
        if cnt == 3:
            ans = max(ans, _sum + a[nx][ny])
        else:
            c[ncx][ncy] = 1
            check(nx, ny, cnt + 1, _sum + a[nx][ny], ncx, ncy)
            c[ncx][ncy] = 0


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

ans = 0
for i in range(n):
    for j in range(m-1):
        _sum = a[i][j] + a[i][j+1]
        if i + 2 < n:
            ans = max(ans, _sum + a[i+1][j] + a[i+2][j])
        if i - 1 >= 0 and i + 1 < n:
            ans = max(ans, max(_sum + a[i+1][j] + a[i-1][j], _sum + a[i+1][j+1] + a[i-1][j+1]))
        c = [[0 for _ in range(4)] for _ in range(5)]
        c[2][0], c[2][1] = 1, 1
        check(i, j+1, 2, _sum, 2, 1)

for j in range(m):
    for i in range(n-1):
        _sum = a[i][j] + a[i+1][j]
        if j + 2 < m:
            ans = max(ans, _sum + a[i][j+1] + a[i][j+2])
        if j - 1 >= 0 and j + 1 < m:
            ans = max(ans, max(_sum + a[i][j+1] + a[i][j-1], _sum + a[i+1][j+1] + a[i+1][j-1]))
        c = [[0 for _ in range(5)] for _ in range(4)]
        c[0][2], c[1][2] = 1, 1
        check(i+1, j, 2, _sum, 1, 2)

print(ans)