백준 14500 테트로미노(Brute-Force, DFS)

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

14500번: 테트로미노

N x M의 보드에 우리가 알고있는 테트리스 블록을 넣었을 때 최대가 되는 값을 구해주는 것이 문제다.

 

1. 5가지 블록을 회전, 뒤집기 모두 가능하기 때문에 모든 경우의 수를 따져서 직접 board에 일일이 해보는 Brute-Force

2. DFS 

 

1번 같은 경우가 바로 생각난 풀이법인데 이렇게 하면 풀리겠지만 별로 하고싶은 문제는 아니였다.

그래서 고민을 해본결과 ㅗ형 블록을 제외하면 나머지도형은 한점에서 시작해서 한붓그리기가 가능한 도형이기 때문에

DFS로 depth == 4 일 때 maxvalue를 계속 갱신해주면 된다고 생각했다.

 

하지만 ㅗ의 경우를 구하는게 매우 난제였다.

충분히 고민해본결과 똑같이 dfs를 돌리다가 cnt가 2가 되는순간 상하좌우를 더한 nx,ny에 대해 다음 dfs를 돌리는게 아닌 x,y에 대해 다시 dfs를 돌리는 것이다.

 

즉 cnt == 2일 땐 상하좌우로 모두 이동가능한 형태인데 cnt == 4일 때 return이 되기 때문에 ㅗ의 회전형태가 나올 것이다.

 

 

import sys
input = sys.stdin.readline

def dfs(x,y,ans,cnt):
    global maxValue

    if cnt == 4:
        maxValue = max(maxValue, ans)
        return

    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if 0 <= nx < n and 0 <= ny < m and not visited[nx][ny]:
            if cnt == 2:
                visited[nx][ny] = 1
                dfs(x,y,ans+data[nx][ny],cnt + 1)
                visited[nx][ny] = 0
            visited[nx][ny] = 1
            dfs(nx, ny, ans + data[nx][ny], cnt + 1)
            visited[nx][ny] = 0

n,m = list(map(int,input().split()))
data = [list(map(int,input().split())) for _ in range(n)]
maxValue = 0

dx = [-1,0,0,1]
dy = [0,1,-1,0]
visited = [[False] * m for _ in range(n)]

for i in range(n):
    for j in range(m):
        visited[i][j] = 1
        dfs(i,j,data[i][j],1)
        visited[i][j] = 0

print(maxValue)