[DFS/BFS] 이코테 (파이썬) 연구소 풀이

[문제]

인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었습니다. 다행히 바이러스는 아직 퍼지지 않았고,

 

바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 합니다.

 

연구소는 크기가 N x M인 직사각형으로 나타낼 수 있으며, 직사각형은 1 x 1 크기의 정사각형으로 나누어져 있습니다.

 

연구소는 빈칸, 벽으로 이루어져 있으며, 벽은 칸 하나를 가득 차지합니다.

 

일부 칸은 바이러스가 존재하며, 이 바이러스는 상하좌우로 인접한 빈칸으로 모두 퍼져나갈 수 있습니다.

 

새로 세울 수 있는 벽의 개수는 3개이며, 꼭 3개를 세워야 합니다.

 

.

.

.

벽을 3개 세운 뒤, 바이러스가 퍼질 수 없는 곳을 안전 영역이라고 할 때 위의 지도에서 안전 영역의 크기는 27입니다.

 

연구소의 지도가 주어졌을 때 얻을 수 있는 안전 영역 크기의 최댓값을 구하는 프로그램을 작성하세요.

 

[입력 조건]

1. 첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어집니다. (3 <= N, M <= 8)

 

2. 둘째 줄부터 N개의 줄에 지도의 모양이 주어집니다. 0은 빈칸, 1은 벽, 2는 바이러스가 있는 위치입니다.

 

   2의 개수는 2보다 크거나 같고, 10보다 작거나 같은 자연수입니다.

 

3. 빈칸의 개수는 3개 이상입니다.

 

[출력 조건]

1. 첫째 줄에 얻을 수 있는 안전 영역의 최대 크기를 출력합니다.

<입력 예시 1>
7 7
2 0 0 0 1 1 0
0 0 1 0 1 2 0
0 1 1 0 1 0 0
0 1 0 0 0 0 0
0 0 0 0 0 1 1
0 1 0 0 0 0 0
0 1 0 0 0 0 0
<출력 예시 1>
27

<입력 예시 2>
4 6
0 0 0 0 0 0
1 0 0 0 0 2
1 1 1 0 0 2
0 0 0 0 0 2
<출력 예시 2>
9

 

 

[내 풀이]

n, m = map(int, input().split())
data = [] # 초기 맵 리스트
temp = [[0] * m for _ in range(n)] # 벽을 설치한 뒤의 맵 리스트

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) :
      if temp[i][j] == 0 :
        score += 1
  return score

# 깊이 우선 탐색(DFS)을 이용해 울타리를 설치하면서, 매번 안전 영역의 크기 계산
def dfs(count) :
  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)

 

---

출처

이것이 코딩 테스트다 with 파이썬 - 나동빈 저