연구소 (feat. 백준, 14502번)

연구소
https://www.acmicpc.net/problem/14502

14502번: 연구소

반응형

DFS 형태의 풀이

# woohyeon.kim
N, M = map(int, input().split())
arr = []
for _ in range(N):
  arr.append(list(map(int, input().split())))
temp = [[0] * M for _ in range(N)]
dx = [-1, 1, 0, 0]
dy = [0, 0, 1, -1]
result = 0
wall_count = 0

def virus(x, y):
  global dx, dy, temp
  for idx in range(len(dx)):
    nx = x + dx[idx]
    ny = y + dy[idx]
    if 0 <= nx < N and 0 <= ny < M:
      if temp[nx][ny] == 0:
        temp[nx][ny] = 2
        virus(nx, ny)

def dfs():
  global wall_count, result
  # 벽이 3개 채워지면
  if wall_count == 3:
    for ix in range(N):
      for iy in range(M):
        temp[ix][iy] = arr[ix][iy]
    # 바이러스 퍼트리기
    for ix in range(N):
      for iy in range(M):
        if temp[ix][iy] == 2:
          virus(ix, iy)
    # 남은 0의 수 구하기
    count = 0
    for ix in range(N):
      for iy in range(M):
        if temp[ix][iy] == 0:
          count += 1
    result = max(result, count)
    return
  
  for ix in range(N):
    for iy in range(M):
      if arr[ix][iy] == 0:
        arr[ix][iy] = 1
        wall_count += 1
        dfs()
        arr[ix][iy] = 0
        wall_count -= 1

dfs()
print(result)
# *&)*@*

BFS 형태의 풀이

from collections import deque

N, M = map(int, input().split())
arr = []
for _ in range(N):
  arr.append(list(map(int, input().split())))
temp = [[0] * M for _ in range(N)]
dx = [-1, 1, 0, 0]
dy = [0, 0, 1, -1]
result = 0
wall_count = 0

def bfs():
  global N,M,temp,dx,dy
  q = deque()
  for ix in range(N):
    for iy in range(M):
      if(temp[ix][iy] == 2):
        q.append([ix,iy])

  while q:
    x, y = q.popleft()
    for idx in range(len(dx)):
      nx = x + dx[idx]
      ny = y + dy[idx]
      if 0 <= nx < N and 0 <= ny < M and temp[nx][ny] == 0:
        temp[nx][ny] = 2
        q.append([nx,ny])
  
def virus(x, y):
  global dx, dy, temp
  for idx in range(len(dx)):
    nx = x + dx[idx]
    ny = y + dy[idx]
    if 0 <= nx < N and 0 <= ny < M:
      if temp[nx][ny] == 0:
        temp[nx][ny] = 2
        virus(nx, ny)

def dfs():
  global wall_count, result
  # 벽이 3개 채워지면
  if wall_count == 3:
    for ix in range(N):
      for iy in range(M):
        temp[ix][iy] = arr[ix][iy]
    # 바이러스 퍼트리기
    bfs()
    # 남은 0의 수 구하기
    count = 0
    for ix in range(N):
      for iy in range(M):
        if temp[ix][iy] == 0:
          count += 1
    result = max(result, count)
    return
  
  for ix in range(N):
    for iy in range(M):
      if arr[ix][iy] == 0:
        arr[ix][iy] = 1
        wall_count += 1
        dfs()
        arr[ix][iy] = 0
        wall_count -= 1

dfs()
print(result)

dfs/bfs간 차이는 없는 것 같습니다.

문제는 둘다 파이썬으로 제출시 시간초과가 나고, pypy3로 제출해야 시간초과가 나지 않습니다.

크게 최적화 할부분이 없는것 같은데,

혹시 아이디어가 있으신분이 계신다면 댓글 부탁드리겠습니다!