테트로미노(14500번)

이 문제를 풀면서 역대급으로 이상한 시행착오를 많이 한 것 같다. 그 풀이 과정을 공유해보고자 한다.

문제

폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다.

정사각형은 서로 겹치면 안 된다.
도형은 모두 연결되어 있어야 한다.
정사각형의 변끼리 연결되어 있어야 한다. 즉, 꼭짓점과 꼭짓점만 맞닿아 있으면 안 된다.
정사각형 4개를 이어 붙인 폴리오미노는 테트로미노라고 하며, 다음과 같은 5가지가 있다.

아름이는 크기가 N×M인 종이 위에 테트로미노 하나를 놓으려고 한다. 종이는 1×1 크기의 칸으로 나누어져 있으며, 각각의 칸에는 정수가 하나 쓰여 있다.

테트로미노 하나를 적절히 놓아서 테트로미노가 놓인 칸에 쓰여 있는 수들의 합을 최대로 하는 프로그램을 작성하시오.

테트로미노는 반드시 한 정사각형이 정확히 하나의 칸을 포함하도록 놓아야 하며, 회전이나 대칭을 시켜도 된다.

코드 1

def bfs(col,row,depth,val):
  global max_val
  val+=war[col][row]
  check[col][row]=False
  if depth>=4:
    max_val=max(max_val,val)
    return
    
  if col>0 and check[col-1][row]:
    bfs(col-1,row,depth+1,val)
  if col<N-1 and check[col+1][row]:
    bfs(col+1,row,depth+1,val)
  if row>0 and check[col][row-1]:
    bfs(col,row-1,depth+1,val)
  if row<M-1 and check[col][row+1]:
    bfs(col,row+1,depth+1,val)      

def plus(col,row):
  global max_val
  if row>0 and row<M-1:
    if col>0:
      max_val=max(max_val,war[col-1][row]+war[col][row-1]+war[col][row+1]+war[col][row])
    if col<N-1:
      max_val=max(max_val,war[col+1][row]+war[col][row-1]+war[col][row+1]+war[col][row])
  if col>0 and col<N-1:
    if row>0:
      max_val=max(max_val,war[col][row-1]+war[col-1][row]+war[col+1][row]+war[col][row])
    if row<M-1:
      max_val=max(max_val,war[col][row+1]+war[col-1][row]+war[col+1][row]+war[col][row])

N,M=map(int,input().split())
war=[]
max_val=0
for _ in range(N):
  war.append(list(map(int,input().split())))
for i in range(N):
  for j in range(M):
    check=[[True]*M for _ in range(N)]
    bfs(i,j,1,0)
    plus(i,j)
print(max_val)

풀이 1

가장 먼저 생각한 풀이였는데 처음부터 끝까지 잘못되었다. 매번 반복문마다 check 배열을 생성해주었는데 이것이 시간초과를 만드는 가장 큰 이유였고, 재귀에서 return할 때, check를 다시 원래대로 바꾸어야 되는데 그것도 하지 않았다. 또한 멍청하게 dfs로 코드를 짜고 있으면서 함수이름은 bfs로 하는 끔찍한 코드를 작성했다.

코드 2

import sys
input=sys.stdin.readline

def bfs(col,row,depth,val,check):
  global max_val
  if max_val>= val+k*(4-depth):
    return
  val+=war[col][row]
  if depth>=4:
    max_val=max(max_val,val)
    return
  check.append((col,row))  
  if col>0 and (col-1,row) not in check:
    bfs(col-1,row,depth+1,val,check)
  if col<N-1 and (col+1,row) not in check:
    bfs(col+1,row,depth+1,val,check)
  if row>0 and (col,row-1) not in check:
    bfs(col,row-1,depth+1,val,check)
  if row<M-1 and (col,row+1) not in check:
    bfs(col,row+1,depth+1,val,check)      

def plus(col,row):
  global max_val
  if row>0 and row<M-1:
    if col>0:
      max_val=max(max_val,war[col-1][row]+war[col][row-1]+war[col][row+1]+war[col][row])
    if col<N-1:
      max_val=max(max_val,war[col+1][row]+war[col][row-1]+war[col][row+1]+war[col][row])
  if col>0 and col<N-1:
    if row>0:
      max_val=max(max_val,war[col][row-1]+war[col-1][row]+war[col+1][row]+war[col][row])
    if row<M-1:
      max_val=max(max_val,war[col][row+1]+war[col-1][row]+war[col+1][row]+war[col][row])

N,M=map(int,input().split())
war=[]
max_val=0
for _ in range(N):
  war.append(list(map(int,input().split())))
k=max(map(max,war))
for i in range(N):
  for j in range(M):
    bfs(i,j,1,0,[])
    plus(i,j)
print(max_val)

풀이 2

나름대로 창의적인 방법이라고 check를 2차원 리스트대신 1차원 리스트로 하고 튜플을 저장하는 방식으로 코드를 작성했는데 python에서 리스트는 기본적으로 call by reference이기 때문에 모든 값이 공유되어 바람직하지 않았다.

코드 3

import sys
input=sys.stdin.readline

def bfs(col,row,depth,val):
  global max_val

  
  check[col][row]=False
  val+=war[col][row]
  if max_val>= val+k*(4-depth):
    check[col][row]=True
    return
  if depth>=4:
    max_val=max(max_val,val)
    check[col][row]=True
    return
  if col>0 and check[col-1][row]:
    # check[col-1][row]=False
    bfs(col-1,row,depth+1,val)
    # check[col-1][row]=True
  if col<N-1 and check[col+1][row]:
    # check[col+1][row]=False
    bfs(col+1,row,depth+1,val)
    # check[col+1][row]=True
  if row>0 and check[col][row-1]:
    # check[col][row-1]=False
    bfs(col,row-1,depth+1,val)
    # check[col][row-1]=True
  if row<M-1 and check[col][row+1]:
    # check[col][row+1]=False
    bfs(col,row+1,depth+1,val) 
    # check[col][row+1]=True
  
  check[col][row]=True


def plus(col,row):
  global max_val
  if row>0 and row<M-1:
    if col>0:
      max_val=max(max_val,war[col-1][row]+war[col][row-1]+war[col][row+1]+war[col][row])
    if col<N-1:
      max_val=max(max_val,war[col+1][row]+war[col][row-1]+war[col][row+1]+war[col][row])
  if col>0 and col<N-1:
    if row>0:
      max_val=max(max_val,war[col][row-1]+war[col-1][row]+war[col+1][row]+war[col][row])
    if row<M-1:
      max_val=max(max_val,war[col][row+1]+war[col-1][row]+war[col+1][row]+war[col][row])

N,M=map(int,input().split())
war=[]
max_val=0
for _ in range(N):
  war.append(list(map(int,input().split())))
k=max(map(max,war))
check=[[True]*M for x in range(N)]
for i in range(N):
  for j in range(M):
    # check[i][j]=False
    bfs(i,j,1,0)
    # check[i][j]=True
    plus(i,j)

print(max_val)

풀이 3

그 이후에도 여러 시행착오를 거듭하고 나서 check 2차원 리스트를 한 번만 생성하고나서 dfs를 시작할 때 check를 바꾸고, return할 때 check를 원래대로 복구해야 된다는 것을 깨달았다. 또한 아래와 같이 남은 값이 모두 배열 내 최대값이라도 기존의 정답보다 작은 경우 return하는 예외처리를 해주면
시간을 훨씬 줄일 수 있다.

if max_val>= val+k*(4-depth):
    check[col][row]=True
    return

오랜만에 dfs 문제를 풀다보니 재귀를 생각하느라 어지러운 문제였다. 특히 경로를 고려하며 dfs 탐색하는 문제에서 visit을 어떻게 처리해야하는지 많이 고민할 수 있었다.