[DFS/BFS] (2) 연구소

이코테 p.341 연구소

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

14502번: 연구소

소스코드

• n과 m 입력 크기가 크지 않기 때문에 벽 3개를 세울 수 있는 모든 경우의 수를 찾을 수 있음
• 동작 방식
  1. DFS를 이용하여 벽 3개를 세울 수 있는 모든 경우의 수 구하기
  2. DFS를 이용하여 바이러스 퍼뜨리기
  3. 바이러스를 퍼뜨린 후의 안전 영역 카운트
  4. 안전 영역의 최댓값 갱신하기

# DFS를 이용하여 빈 칸에 벽 3개를 세울 수 있는 모든 경우의 수를 찾고
# DFS를 이용하여 바이러스를 퍼뜨린 후의 안전 영역의 최댓값 찾기

import sys
input = sys.stdin.readline

# 입력 받기
n, m = map(int, input().split())

graph = [] # 초기 맵 리스트
for _ in range(n):
  graph.append(list(map(int, input().split())))

# 벽을 설치한 뒤의 맵 리스트
temp = [[0] * m for _ in range(n)]

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

# 바이러스를 퍼뜨리는 함수
def virus(x, y):
  for i in range(4): # 현재 좌표의 상하좌우에 대하여
    nx = x + dx[i]
    ny = y + dy[i]
    if nx >= 0 and nx < n and ny >= 0 and ny < m:
      if temp[nx][ny] == 0: # 벽이 없는 경우
        temp[nx][ny] = 2 # 바이러스 퍼뜨리기
        virus(nx, ny) # 현재 좌표를 기준으로 재귀적으로 바이러스 퍼뜨리기

# 안전 영역의 개수를 카운트하는 함수
def count_safety():
  safety = 0
  for i in range(n):
    for j in range(m):
      if temp[i][j] == 0:
        safety += 1
  return safety

result = 0 # 안전 영역의 최댓값
def dfs(count):
  global result
  if count == 3: # 벽 3개를 설치한 경우
    for i in range(n):
      for j in range(m):
        temp[i][j] = graph[i][j]
    # 바이러스 전파 수행
    for i in range(n):
      for j in range(m):
        if temp[i][j] == 2:
          virus(i, j) # 바이러스 퍼뜨리기
    safety = count_safety() # 안전 영역의 개수
    result = max(result, safety) # 안전 영역의 최댓값 갱신
    return
    
  for i in range(n):
    for j in range(m):
      if graph[i][j] == 0:
        graph[i][j] = 1 # 벽 설치
        count += 1 # 설치한 벽의 개수 +1
        dfs(count)
        graph[i][j] = 0 # 벽 제거
        count -= 1 # 설치한 벽의 개수 -1

dfs(0)
print(result)

• python3로 하면 시간초과가 뜨는데 pypy3로 하면 정답 처리됨...