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

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

14500번: 테트로미노

---

아이디어

1. 두 가지로 나눠 생각하면

• 테트로미노 도형 만들기
• 종이 위에 올리기 

2. 도형 만들기

• 도형이 회전이나 대칭도 가능하니 dfs를 사용하면 T도형 빼고 전부 다 만들 수 있다.
• dfs 탐색 깊이를 4까지 설정하면 도형을 확인할 수 있다.
• T 모양은 따로 함수를 만들어 처리했다.

3. 종이에 도형 놓기

• 시간제한이나 N, M 크기를 보고 브루트 포스를 사용하기로 결정했다.
• 각 위치마다 만들어지는 모든 도형의 최댓값들을 모아 전체 비교를 해준다.

 

---

코드 설명

def dfs(x,y,n,c):
    global dfs_max
    if c == 4:
        if dfs_max < n:
            dfs_max = n
    else:
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < N and 0 <= ny < M:
                if visited[nx][ny] == 0:
                    visited[nx][ny] = 1
                    dfs(nx,ny,n + paper[nx][ny],c + 1)
                    visited[nx][ny] = 0

딱히 특이사항이 없는 dfs코드

 

def t_spin(x,y):
    t_max = 0
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if 0 <= nx < N and 0 <= ny < M: # +1칸
            nnx = nx + dx[i]
            nny = ny + dy[i]
            if 0 <= nnx < N and 0 <= nny < M: # +2칸
                    for h in [-1,1]: #볼록한 부분
                        value = paper[x][y]
                        if i == 0 or i == 1: #세로로 길면
                            sny = ny + h
                            if 0 <= sny < M:
                                value += paper[nx][ny]
                                value += paper[nnx][nny]
                                value += paper[nx][sny]
                        elif i == 2 or i == 3: #가로로 길면
                            snx = nx + h
                            if 0 <= snx < N:
                                value += paper[nx][ny]
                                value += paper[nnx][nny]
                                value += paper[snx][ny]
                        if t_max < value:
                            t_max = value
    return t_max

좀 무식한 방법이지만 for문을 사용해서 가능한 모든 T모양을 체크한다. 

 

---

전체 코드

import sys
N, M = map(int,input().split())
input = sys.stdin.readline
dx = [-1, 1, 0, 0] # 북, 남, 서, 동
dy = [0, 0, -1, 1]
paper = []
ans = 0

#   @@@@   @@
#          @@
#   @  @
#   @  @@  @@@
#   @@  @   @

for i in range(N):
    paper.append([int(x) for x in input().split()])

visited = [[0 for _ in range(M)] for _ in range(N)]

def dfs(x,y,n,c):
    global dfs_max
    if c == 4:
        if dfs_max < n:
            dfs_max = n
    else:
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < N and 0 <= ny < M:
                if visited[nx][ny] == 0:
                    visited[nx][ny] = 1
                    dfs(nx,ny,n + paper[nx][ny],c + 1)
                    visited[nx][ny] = 0

def t_spin(x,y):
    t_max = 0
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if 0 <= nx < N and 0 <= ny < M: # +1칸
            nnx = nx + dx[i]
            nny = ny + dy[i]
            if 0 <= nnx < N and 0 <= nny < M: # +2칸
                    for h in [-1,1]: #볼록한 부분
                        value = paper[x][y]
                        if i == 0 or i == 1: #세로로 길면
                            sny = ny + h
                            if 0 <= sny < M:
                                value += paper[nx][ny]
                                value += paper[nnx][nny]
                                value += paper[nx][sny]
                        elif i == 2 or i == 3: #가로로 길면
                            snx = nx + h
                            if 0 <= snx < N:
                                value += paper[nx][ny]
                                value += paper[nnx][nny]
                                value += paper[snx][ny]
                        if t_max < value:
                            t_max = value
    return t_max

for i in range(N):
    for j in range(M):
        dfs_max = 0
        visited[i][j] = 1
        dfs(i,j,paper[i][j],1)
        visited[i][j] = 0
        block_max = max(dfs_max, t_spin(i, j))
        ans = max(ans,block_max)

print(ans)