[Python/파이썬] - 백준(BOJ) 14500번 : 테트로미노

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

14500번: 테트로미노

 

DFS를 이용하여 4칸 탐색을 하면 T자 모양 테트로미노 제외한 모든 모양을 확인할 수 있다.

DFS를 이용해 T자 제외 테트로미노의 최대합을 max함수를 이용하여 전역변수 answer에 저장해둔 후

T자 테트로미노를 탐색하여 answer의 최댓값을 조정한다.

이후에 answer값을 출력하면 된다.

 

DFS를 이용할 때는 중복 체크를 위해 함수 시작부분에 visit[y][x] = 1을 하였고

다른 모양의 테트로미노를 사용할 때 잘못된 중복체크를 막기 위해 종료 전 visit[y][x] = 0을 하였다.

 

코드 :

import sys
input = sys.stdin.readline

answer = 0
def DFS(y, x, s, v):
    global answer
    if v == 4:
        answer = max(answer, s)
        return
    visit[y][x] = 1
    for i in range(4):
        yy = y + dy[i]
        xx = x + dx[i]
        if 0 <= yy < n and 0 <= xx < m and visit[yy][xx] == 0:
            DFS(yy, xx, s+arr[yy][xx], v+1)
    visit[y][x] = 0
def T(y, x):
    global answer
    for k in range(4):
        s = arr[y][x]
        b = 1
        for i in range(4):
            if i == k:
                continue
            yy = y + dy[i]
            xx = x + dx[i]
            if yy < 0 or xx < 0 or yy >= n or xx >= m:
                b = 0
                break
            s += arr[yy][xx]
        if b:
            answer = max(answer, s)
n, m = map(int,input().split())
arr = [list(map(int,input().split())) for _ in range(n)]
visit = [[0 for _ in range(m)] for _ in range(n)]
dy = [0,1,0,-1]
dx = [1,0,-1,0]
for i in range(n):
    for j in range(m):
        DFS(i, j, 0, 0)
        T(i, j)
print(answer)