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

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

14500번: 테트로미노

 

 

구현 문제입니다.

정사각형 네칸으로 만든 테트로미노의 모양으로 탐색을 하여 answer값을 max로 만드는 문제입니다.

우선 처음에 모든 테트로미노가 네칸이므로 dy, dx 배열을 만들어 만들어질 수 있는 경우의 수를 DFS로 탐색하였습니다.

DFS로 네 방향 모두 탐색을 하며 탐색을 시작할 때 visit 배열의 값을 1로 만들어 중복을 피하고

탐색이 끝난 경우 visit을 다시 0으로 전환하여 모든 경우의 수를 탐색하도록 하였습니다.

네칸을 탐색하였다면 저장해둔 값과 answer값을 max함수를 이용하여 비교하여 최대값으로 저장해줍니다.

 

이 알고리즘을 통하여 모두 탐색할 수 있을 줄 알았는데 T자 모양은 DFS로 탐색이 불가능하여 따로 함수를 생성해주었습니다.

첫번째 칸 근처의 세칸을 탐색하도록 만들었습니다.

 

 

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)