[백준 14500번-파이썬]테트로미노

백준 (BOJ) 14500
https://www.acmicpc.net/problem/14500

사용언어 : PYTHON

1.문제

 

2.풀이

브루트포스 알고리즘을 사용하는 문제이다. ( 다른 풀이를 추가하였습니다)
시간제한은 2초인데 1억=1초의 룰에 대입했을때 2천8백만이 나오므로 브루트포스 알고리즘을 사용해도 된다.
499*499*19*6 = 28,386,114

회전 또는 대칭으로 만들 수 있는 모든 테트로미노를 1과 0의 배열로 만든다.

19개의 테트로미노들을 돌아가며 종이의 모든 배치 가능한 구역에 배치한다.

그리고 모든 배치중에서 최댓값을 찾는다.

이 문제를 통해서 연산이 복잡해 질 때는 함수를 사용하여 복잡한 연산들을 분할하면 좀 더 쉽게 구현할 수 있음을 알게되었다.

3.코드

import sys
import math
input = sys.stdin.readline

N,M = map(int,input().split())
paper=[list(map(int,input().split())) for _ in range(N)]

tetros=[
    [[1,1,1,1]],
    [[1],[1],[1],[1]],
    [[1,1],[1,1]],
    [[1,0],[1,0],[1,1]],
    [[1,1,1],[1,0,0]],
    [[1,1],[0,1],[0,1]],
    [[0,0,1],[1,1,1]],
    [[0,1],[0,1],[1,1]],
    [[1,1,1],[0,0,1]],
    [[1,1],[1,0],[1,0]],
    [[1,0,0],[1,1,1]],
    [[1,0],[1,1],[0,1]],
    [[0,1,1],[1,1,0]],
    [[0,1],[1,1],[1,0]],
    [[1,1,0],[0,1,1]],
    [[1,1,1],[0,1,0]],
    [[0,1],[1,1],[0,1]],
    [[0,1,0],[1,1,1]],
    [[1,0],[1,1],[1,0]]
]

def calc(t,i,j,paper): # 현재 tetro가 배치된 종이의 값을 계산하는 함수
    h,w = len(t),len(t[0])

    result=0

    for p in range(h):
        for q in range(w):
            result+=t[p][q]*paper[i+p][j+q]

    return result

def place(t,n,m,paper): # 전달받은 tetro를 종이의 모든 경우에 배치하고 최댓값을 리턴하는 함수
    h,w = len(t),len(t[0])
    result=0

    for i in range(n-h+1):
        for j in range(m-w+1):
            tmp=calc(t,i,j,paper) # 현재 tetro가 배치된 종이의 값을 계산하는 함수
            if tmp>result:
                result=tmp

    return result


max_tetro=0

for tetro in tetros: # 모든 tetro를 순회하면서 종이에 배치한다.
    tmp=place(tetro,N,M,paper) 
    if max_tetro < tmp:
        max_tetro=tmp

print(max_tetro)

 

 

다른 풀이

ㅗ 모양을 제외한 나머지 모양들은 하나의 시작점에서 세 칸을 연속으로 이동할 수 있는 모든 경우를 조회하면 된다.

 

• ㅗ모양을 제외한 나머지 모양 : solve() 함수에서 모든 점에 대해 연속으로 3 칸 이동하는 dfs를 수행한다
• ㅗ모양 : exSolve() 함수에서 모든 점에 대해 (위,오른쪽, 아래) (오른쪽,아래,왼쪽) (아래,왼쪽,위) (왼쪽,위,오른쪽) 을 방문하는 dfs를 수행한다

import sys

input = sys.stdin.readline

dr = [-1, 0, 1, 0]
dc = [0, 1, 0, -1]


def solve(r, c, n):
    global answer

    if n == 3:
        result = 0
        for i in range(4):
            result += l[p[i][0]][p[i][1]]

        answer = result if result > answer else answer

        return


    for d in range(4):
        nr = r + dr[d]
        nc = c + dc[d]
        if nr<0 or nr>=N: continue
        if nc<0 or nc>=M: continue
        if not chk[nr][nc]:
            chk[nr][nc]=True
            p.append([nr,nc])
            solve(nr,nc,n+1)
            chk[nr][nc]=False
            p.pop()

def exSolve(r,c,d,n):
    global answer

    if n==3:
        result = 0
        for a in p:
            result += l[a[0]][a[1]]

        answer = result if result > answer else answer

        return

    for di in range(d+1,4):
        nr = r + dr[di]
        nc = c + dc[di]
        if nr<0 or nr>=N: continue
        if nc<0 or nc>=M: continue
        p.append([nr,nc])
        exSolve(r,c,di,n+1)
        p.pop()




N, M = map(int, input().split())

l = [list(map(int, input().split())) for _ in range(N)]

chk = [[False] * M for _ in range(N)]
p = []
answer = 0
for i in range(0,N):
    for j in range(0,M):
        p.append([i,j])
        chk[i][j]=True
        solve(i,j,0)
        p.pop()
        chk[i][j]=False


p.clear()

for i in range(0,N):
    for j in range(0,M):
        p.append([i,j])
        exSolve(i,j,-1,0)
        p.pop()

print(answer)