[ 이것이 취업을 위한 코딩 테스트다 with 파이썬 ] Chapter 13 DFS/BFS 문제 - Q16 연구소

1) 문제

 

 

2) 코드

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

# 문제에서 주어진 map 초기값
data = []

# 벽을 세운 map 
temp = [[0] * m for _ in range(n)]

# 문제에서 주어진 map 만들기
for _ in range(n):
  data.append(list(map(int, input().split())))

# 4가지 이동 방향 (동, 북, 서, 남)
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]

# 안전 영역 개수
result = 0

# DFS 를 이용해서 각 바이러스가 사방으로 퍼지도록 하는 함수
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 get_score():
  score = 0
  for i in range(n):
    for j in range(m):
      # 영역의 값이 0 인 곳 카운트 하기
      if temp[i][j] == 0:
        score += 1
  return score

# DFS 를 이용해 울타리 설치 & 안전 영역 크기 계산
def dfs(count):
  # result 값 전역 변수로 선언
  global result
  # 울타리 3개 설치된 경우, 결과 맵 완성하기
  if count == 3:
    for i in range(n):
      for j in range(m):
        temp[i][j] = data[i][j]
    # 바이러스 전파 시키기
    for i in range(n):
      for j in range(m):
        if temp[i][j] == 2:
          virus(i, j)
    # 안전 영역의 최댓값 게산
    result = max(result, get_score())
    return
  # 빈 공간에 울타리 설치
  for i in range(n):
    for j in range(m):
      if data[i][j] == 0:
        data[i][j] = 1
        count += 1
        dfs(count)
        data[i][j] = 0
        count -= 1


dfs(0)
print(result)

 

3) 마치며

어려워서 답지 보면서 하나하나 이해하면서 코드 작성했땅,,