[백준][python]14500 테트로미노

Algorithm

[백준][python]14500 테트로미노

soduddl1 2023. 4. 26. 20:20

문제

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

소스코드

import sys
input = sys.stdin.readline
from itertools import combinations

if __name__ == "__main__":
    n,m = map(int,input().split())
    arr = [list(map(int,input().split())) for _ in range(n)]
    answer = 0
    visited = [[0] * m for _ in range(n)]
    move = [[1,0],[-1,0],[0,1],[0,-1]] # 상,하,좌,우

    # ㅗ 제외 테트로미노 체크
    def dfs(l,x,y,tmp_sum):
        global answer
        if l == 4: # 폴리오미노 4개를 두면 테트로미노
            answer = max(answer,tmp_sum)
            return
        for k in range(4): # 이전과 연속해서 상하좌우 체크
            xx = x + move[k][0]
            yy = y + move[k][1]
            if 0 <= xx < n and 0 <= yy < m and not visited[xx][yy]:
                visited[xx][yy] = 1
                dfs(l+1,xx,yy,arr[xx][yy]+tmp_sum)
                visited[xx][yy] = 0 # 반드시 백트래킹

    # ㅗ 테트로미노 체크
    def chk(x,y):
        global answer
        for ch in list(combinations([i for i in range(4)],3)): # 중심 제외 상하좌우 중 3개 선택해서 체크해야 함
            tmp = arr[x][y] # 초기값은 가운데 중심
            for c in ch: # 상하좌우 중 3개 선택한 값 체크
                xx = x + move[c][0]
                yy = y + move[c][1]
                if 0 <= xx < n and 0 <= yy < m:
                    tmp += arr[xx][yy]
                else: #경로 이탈하면
                    tmp = 0 #전부 탈락 이 테트로미노는 못들어옴
                    break
            answer = max(answer,tmp)

    for i in range(n):
        for j in range(m):
            # ㅗ 제외 테트로미노 체크
            visited[i][j] = 1
            dfs(1,i,j,arr[i][j])
            visited[i][j] = 0
            # ㅗ 테트로미노 체크
            chk(i,j)

    print(answer)