[이것이 취업을 위한 코딩테스트다]연구소-Python[파이썬]

책 <이것이 취업을 위한 코딩 테스트다 with 파이썬>

p.342쪽 <연구소>

알고리즘

0 : 빈칸, 1 : 벽, 2 : 바이러스 있는 곳

• g_lst : graph값이 0인 곳 즉 빈칸인 곳을 모아둔 set 자료형. g_lst에서 임의로 3개의 값을 뽑아서 벽을 세울 것이다. 이때 3개 뽑는 모든 경우의 수는 combinations 함수를 사용하여 모두 구한다.

• v_lst : 초기 바이러스의 위치 (i, j)를 모아둔 리스트이다.

• combinations함수를 사용하여 모든 경우의 수를 구하고 for문을 통해 이 모든 경우를 따져본다. 이때 각 경우에서 바이러스가 전파된 결과도 구해야하는데 이는 bfs를 통해 구현했다.
  이때 새롭게 전염된 곳으로부터 다시 바이러스가 전파되므로 bfs의 마지막 코드에 bfs함수를 재귀호출 해줘야한다.

• 바이러스가 전파된 결과에 0의 개수를 세고 모든 경우의 수를 따져가며 0의 개수가 최대가 되는 값을 찾는다.

• 모든 경우의 수를 따져볼 때, graph는 원본 상태를 유지하면서 copy 해줘야한다. 나는 처음에 그냥 t_graph = graph.copy()로 작성했는데 이것은 graph의 원본도 같이 바뀌는 얕은 복사였다..(같은 주소를 가리킴)
  원본을 보존할 수 있는 깊은 복사를 하려면 copy를 import해주고 t_graph = copy.deepcopy(graph) 이렇게 작성해야한다!
  (이것때문에 30분은 헤맸다ㅜㅜ)

코드

from collections import deque
from itertools import combinations as cb
import copy
def bfs(t_graph, start): # start : (i, j)
    q = deque([start])
    while q:
        si, sj = q.popleft()
        for di, dj in zip(di_lst,dj_lst):
            ni = si + di
            nj = sj + dj
            if ni >= 0 and ni < n and nj >= 0 and nj < m and t_graph[ni][nj]==0:
                t_graph[ni][nj] = 2
                bfs(t_graph, (ni, nj)) # 새롭게 전염된 곳으로부터 다시 바이러스 전파되므로 bfs를 재귀 호출


n, m = map(int, input().split())
graph = []
for i in range(n):
    graph.append(list(map(int, input().split())))

# 동 서 남 북
di_lst = [0, 0, 1, -1]
dj_lst = [1, -1, 0, 0]

g_lst = set() # graph값이 0인 좌표들 모임
v_lst = [] # 바이러스 리스트 (i, j)
for i in range(n):
    for j in range(m):
        if graph[i][j] == 0:
            g_lst.add(i*m +j)
        if graph[i][j] == 2:
            v_lst.append((i, j))

max_cnt = 0
g_results = cb(g_lst, 3)
for g_result in g_results:
    t_graph = copy.deepcopy(graph)
    for g in g_result: # 3개 뽑은 결과들 중 하나, ex)  g_result : (1, 5, 20)
        t_graph[g//m][g%m] = 1 # 두번째 for문 돌면서, 3개의 벽 세우기
    for v in v_lst:
        bfs(t_graph, v)
    # 0개수 세기
    cnt = 0
    for i in range(n):
        cnt += t_graph[i].count(0)   
    max_cnt = max(cnt, max_cnt)
print(max_cnt)