[PS] BOJ145000 테트로미노 ( BackTracking ) With 파이썬

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

14500번: 테트로미노

 

◎ 문제풀이

 

굉장히 어려운 문제였다. 

인터넷에서 풀이법을 찾아보았는데 다른 사람들도 노가다 한 사람을 제외하면 대부분 풀이를 참고해서 푼거 같다.

 

1. DFS 구현 및 발상

2. 최대값 가지치기 ( 백트래킹 )

 

두 가지 요소를 구현하기 어려웠다.

 

1. DFS 구현 및 발상

 

완전탐색을 할 때 DFS 알고리즘(재귀호출)을 사용해야 한다. 그 이유는 아래 포스팅에 잘 설명되어 있다. 

 

백준 14500 테트로미노

 

위 링크의 풀이는 DFS가 'ㅗ' 모형을 탐색하지 못한다. 그래서  'ㅗ' 모형의 경우를 탐색하는 함수를 추가로 만들어야 한다. 추가로 만들지 않고 DFS 함수 하나로 모든 경우를 탐색하는 방법이 있다. 이는 아래 포스팅에 잘 설명되어 있다.

 

 

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

 

 

2. 최대값 가지치기 ( 백트래킹 )

 

DFS만 구현해도 문제를 풀 수 있지만 시간이 엄청 걸린다. 이때 백트래킹을 적용하면 처리시간을 줄일 수 있다. 최소값 가지치기가 아닌 최댓값 가지치기를 해야한다.

 

max_value = max(map(max,board)) # 입력받은 이차원 배열에서 가장 큰 값 추출
#DFS
def dfs(x,y,current,length) :
  global ans
  if ans >= current + max_value*(4-length) : return
  #중략...

 

ans는 최댓값이 들어가야 한다. 현재까지 합(current)에서 가장 최댓값을 남은 블록만큼 더해도 ans보다 작거나 같다면 가지치기를 한다. 

 

 

◎ 코드

 

최적화된 코드  

#BOJ14500 테트로미노
import sys
input = sys.stdin.readline 

n,m = map(int,input().split())
board = [list(map(int,input().split())) for _ in range(n) ]
visited = [[False for _ in range(m)] for _ in range(n)] 

max_value = max(map(max,board)) #최대값

dx = [0,0,1,-1]
dy = [1,-1,0,0]
ans = 0 #결과

#유효성검사
def isvalidate(x,y) :
  if x >= 0 and y >= 0 and x < m and y < n : return True
  else : return False

#DFS
def dfs(x,y,current,length) :
  global ans
  if ans > current + max_value*(4-length) : return # 가지치기(백트래킹)
  if length == 4 : #블록이 4개인 경우
    ans = max(ans,current)
    return 
    
  for i in range(4) :
    nx = x + dx[i] 
    ny = y + dy[i] 
    if isvalidate(nx,ny) and not visited[ny][nx] :
        if length == 2 : # 'ㅗ' 모형이 가능하도록 좌표 유지
          visited[ny][nx] = True
          dfs(x,y,current+board[ny][nx],length+1)
          visited[ny][nx] = False
        visited[ny][nx] = True
        dfs(nx,ny,current+board[ny][nx],length+1)
        visited[ny][nx] = False

#문제풀이
for i in range(n) :
  for j in range(m) :
    visited[i][j] = True
    dfs(j,i,board[i][j],1)
    visited[i][j] = False
    
print(ans)

 

'ㅗ' 따로 계산한 코드

#BOJ14500 테트로미노
import sys
input = sys.stdin.readline 

n,m = map(int,input().split())
board = [list(map(int,input().split())) for _ in range(n) ]
visited = [[False for _ in range(m)] for _ in range(n)] 

max_value = max(map(max,board))

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

#'ㅗ' 이동 좌표
t = [
  [(1,0),(-1,0),(0,-1)],
  [(1,0),(-1,0),(0,1)],
  [(0,1),(0,-1),(1,0)],
  [(0,1),(0,-1),(-1,0)]
]

ans = 0

#유효성검사
def isvalidate(x,y) :
  if x >= 0 and y >= 0 and x < m and y < n : return True
  else : return False

#DFS
def dfs(x,y,total,lengh) :
  global ans

  if ans > total + max_value*(4-lengh) : return
  if lengh == 4 : #길이가 4인 경우
    ans = max(ans,total)
    return 
    
  for i in range(4) :
    nx = x + dx[i] 
    ny = y + dy[i] 
    if isvalidate(nx,ny) and not visited[ny][nx] :
        visited[ny][nx] = True
        dfs(nx,ny,total+board[ny][nx],lengh+1)
        visited[ny][nx] = False

# 'ㅗ' 모양
def tshape(x,y) :
  total = 0
  for i in range(4) :
    tmp = board[y][x]
    flag = True
    for j in range(3) :
      position = t[i][j] 
      tx = position[0]
      ty = position[1]
      nx = x + tx
      ny = y + ty
      if isvalidate(nx,ny) :
        tmp += board[ny][nx]
      else : flag = False

    total = ( max(total,tmp) if flag else total )
  return total

#문제풀이
for i in range(n) :
  for j in range(m) :
    visited[i][j] = True
    dfs(j,i,board[i][j],1)
    visited[i][j] = False
    ans = max(ans,tshape(j,i))
    
print(ans)