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

문제 링크

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

14500번: 테트로미노

풀이 - 다른 블로그 참고 

- 여기서 알아야할 것은 'ㅜ' 모양을 제외한 다른 모든 테트로미노는 정사각형을 4번 연결하여 만들어진 모양이다. 

따라서 dfs 를 4번 실행하여 모양에 해당하는 최댓값을 찾으면 된다. 

- 'ㅜ'모양은 정사각형 두 개를 연결한 다음 해당 위치에서 다음 정사각형으로 이동하지 않고 다음 위치는 방문 표시 하되, 현재 위치에서 탐색하면 된다. 

- 시간 복잡도를 줄이기 위해 graph에 최댓값을 저장해두고 만약 지금까지 칸 수의 합이 남은 칸수가 모두 최댓값이라고 했을 때의 합보다 크다면 return 한다. 

dx = [ 1, -1, 0, 0 ]
dy = [ 0, 0, 1, -1 ]

def dfs(x, y, result, cnt):
  global answer
  
  # 정사각형 4칸일 때 
  if cnt == 4:
    # 최댓값 갱신 
    answer = max(answer,result)
  if result + (4-cnt) * max_num < answer:
    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]:
      visited[nx][ny]= True
      # "ㅜ" 모양 탐색 
      if cnt== 2 :
        dfs(x, y, result+ graph[nx][ny], cnt + 1 )
      dfs(nx, ny, result+ graph[nx][ny] , cnt + 1)
      visited[nx][ny]= False
  
  return

n, m = map(int,input().split())

graph = []

visited = [ [False] * m for _ in range(n) ]

answer = 0 

for _ in range(n):
  graph.append(list(map(int,input().split())))

# 최댓값 저장 
max_num = max(map(max,graph))

for i in range(n):
  for j in range(m):
    visited[i][j] = True
    # 현재 위치, 결과의 합, 칸 수 
    dfs(i,j,graph[i][j], 1)
    visited[i][j] = False

print(answer)