[Python] 백준 14502 연구소

🧑‍💻 [Python] 백준 14502 연구소

Gold 4 - 구현

from copy import deepcopy

• 깊은 복사를 하는 것이다
• 깊은 복사를 하면, 완전 다른 인스턴스가 만들어진다 (남남이 되는 것)

 

combinations 을 사용해서 배치할 벽들의 좌표를 구했다

• empty_space 리스트에 비어 있는 공간들의 좌표들을 넣었다

 

비어있는 공간들의 좌표의 순열을 통해 벽들을 배치하고, 바이러스가 얼마나 퍼지는지 구하는 것

• for empty in combinations(empty_space, 3):
  • 비어있는 공간들의 좌표 3개를 통해 벽들을 배치해준다

 

BFS를 하는데, BFS는 마지막에 퍼진 바이러스의 개수를 반환해준다

 

퍼진 바이러스의 개수의 최소값을 구하면 된다

 

코드 디테일

queue = deque()
empty_space = []
empty_count = 0
result = N * M

for i in range(N):
    for j in range(M):
        if virus_map[i][j] == 2:
            queue.append((i, j))
        elif virus_map[i][j] == 0:
            empty_space.append((i,j))
            empty_count += 1

• 밑작업
• empty_space는 벽을 설치하게 필요한 비어 있는 공간들의 좌표
• empty_count는 제일 마지막에 값을 구하기 위해 필요한 값이다
• queue는 제일 처음에 바이러스의 위치들을 넣는다

for empty in combinations(empty_space, 3):
    temp_map = deepcopy(virus_map)
    virus_queue = deepcopy(queue)

    for e in empty:
        temp_map[e[0]][e[1]] = 1

    result = min(bfs(temp_map, virus_queue), result)

• 빈 공간에 3개의 벽을 설치한다
• temp_map는 virus_map을 깊은 복제를 한 것이다
• virus_queue는 queue를 깊은 복제 한 것이다
• for e in empty: 을 통해서 지도에 벽을 설치한다

---

 

코드

from collections import deque
from itertools import combinations
from copy import deepcopy

N, M = map(int, input().split())

virus_map = [list(map(int, input().split())) for _ in range(N)]

def bfs(temp_virus, virus_queue):

    dr, dc = [-1, 0, 0, 1], [0, -1, 1, 0]

    virus_count = 2

    while virus_queue:
        r, c = virus_queue.popleft()

        for i in range(4):
            sr, sc = dr[i] + r ,dc[i] + c

            if 0 <= sr < N and 0 <= sc < M:
                if temp_virus[sr][sc] == 0:
                    virus_count += 1
                    temp_virus[sr][sc] = 2
                    virus_queue.append((sr, sc))

    return virus_count

queue = deque()
empty_space = []
empty_count = 0
result = N * M

for i in range(N):
    for j in range(M):
        if virus_map[i][j] == 2:
            queue.append((i, j))
        elif virus_map[i][j] == 0:
            empty_space.append((i,j))
            empty_count += 1


for empty in combinations(empty_space, 3):
    temp_map = deepcopy(virus_map)
    virus_queue = deepcopy(queue)

    for e in empty:
        temp_map[e[0]][e[1]] = 1

    result = min(bfs(temp_map, virus_queue), result)

print(empty_count - (result + 1))