[BOJ] 14500번 테트로미노 (Python) [삼성 SW 역량 테스트 기출 문제]

문제

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

풀이

DFS, BFS로 4칸 탐색한다고 생각하고 접근했다가 실패했다.

다음 모양은 방문했던 곳으로 돌아와야 한다.

대각선 방향도 가능하도록 하되, 접하는 방문한 영역이 존재해야한다는 부분에 착안해서 DFS, BFS의 틀을 유지하면서 코드를 추가했다. 이때, python으로는 시간초과가 나서 pypy로 제출했다.

• DFS에서 다른 DFS에 영향을 주지 않기 위해 원복해야 하는걸 명심해야 할 듯.
• 매번 초기화하는게 아닌 원복해주는걸 통해 시간복잡도를 왕창 줄일 수 있다.

+) 어떨때 global 필요한지 조사 필요
=> 팁 아티클에 작성완료

def is_valid(x,y):
  if 0<=x<N and 0<=y<M and not visited[x][y]:
    return True
  return False

def dfs(x,y,cnt,cum_sum):
  global max_sum # 값의 변경이 필요하므로
  
  if cnt == 4:
    max_sum = max(max_sum, cum_sum)
    return

  for dx, dy in direction:
    new_x,new_y = x+dx, y+dy
    if is_valid(new_x, new_y):
      visited[new_x][new_y]=True
      dfs(new_x, new_y, cnt+1, cum_sum+paper[new_x][new_y])

direction = [(0,1),(1,0),(0,-1),(-1,0)]
N, M = map(int, input().split())
paper = [list(map(int, input().split())) for _ in range(N)]

max_sum = -float('inf')
for i in range(N):
  for j in range(M):
    visited = [[False]*M for _ in range(N)] # 방문여부 초기화
    visited[i][j] = True
    dfs(i,j,1,paper[i][j])
print(max_sum)

import sys
input=sys.stdin.readline

def is_valid(x,y):
  if 0<=x<N and 0<=y<M and not visited[x][y]:
    return True
  return False

def is_valid_diag(x,y): # 이동할 곳 x,y기준 붙어있는 곳 하나 있어야 됨
  if 0<=x<N and 0<=y<M and not visited[x][y]:
      for dx, dy in direction:
        if 0<=x+dx<N and 0<=y+dy<M and visited[x+dx][y+dy]:
          return True
  return False

def dfs(x,y,cnt,cum_sum):
  global max_sum # 값의 변경이 필요하므로
  
  if cnt == 4:
    max_sum = max(max_sum, cum_sum)
    return

  for dx, dy in direction: # 수평, 수직 이동
    new_x,new_y = x+dx, y+dy
    if is_valid(new_x, new_y):
      visited[new_x][new_y]=True # 다른 DFS의 visited에도 영향을 미친다
      dfs(new_x, new_y, cnt+1, cum_sum+paper[new_x][new_y])
      visited[new_x][new_y]=False # 다시 False로 둬야 다른 DFS에 영향 안미친다

  for dx, dy in diagonal: # 대각선 이동
    new_x, new_y = x+dx, y+dy
    if is_valid_diag(new_x,new_y):
      visited[new_x][new_y]=True
      dfs(new_x, new_y, cnt+1, cum_sum+paper[new_x][new_y])
      visited[new_x][new_y]=False

direction = [(0,1),(1,0),(0,-1),(-1,0)] # 수직, 수평 방향
diagonal = [(1,1),(-1,-1),(1,-1),(-1,1)] # 대각선 방향
N, M = map(int, input().split())
paper = [list(map(int, input().split())) for _ in range(N)]

max_sum = -float('inf')
visited = [[False]*M for _ in range(N)] # 방문여부 초기화 1번만
for i in range(N):
  for j in range(M):
    visited[i][j] = True
    dfs(i,j,1,paper[i][j])
    visited[i][j] = False # 매번 초기화하는대신 여기서 다시 원복
print(max_sum)