[백준][Python] 14502 연구소

그래프, bfs, 브루트포스 / 골드 4

🦠

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

14502번: 연구소

 

 

내 풀이

from itertools import combinations
from collections import deque
import copy

def bfs():
    cnt = 0
    q = deque()
    for j in virus:
        q.append((j[0], j[1]))

    while q:
        cx, cy = q.popleft()

        for k in range(4):
            nx, ny = cx + dx[k], cy + dy[k]

            if 0 <= nx < N and 0 <= ny < M and temp[nx][ny] == 0:
                temp[nx][ny] = 2
                q.append((nx, ny))

    for a in range(N):
        cnt += temp[a].count(0)

    return cnt


N, M = map(int, input().split())
arr = [[]*M for _ in range(N)]
wall = []
virus = []
ans = 0

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

for i in range(N):
    arr[i] = list(map(int, input().split()))

for i in range(N):
    for j in range(M):
        if arr[i][j] == 0:
            wall.append([i, j])
        elif arr[i][j] == 2:
            virus.append([i, j])

wall_list = list(combinations(wall, 3))

for i in wall_list:
    temp = copy.deepcopy(arr)
    temp[i[0][0]][i[0][1]] = 1
    temp[i[1][0]][i[1][1]] = 1
    temp[i[2][0]][i[2][1]] = 1

    ans = max(ans, bfs())

print(ans)

 

 

코드 설명

 

지도 전체를 검사하며, 벽의 좌표와 바이러스의 좌표를 각 리스트에 추가한다.

for i in range(N):
    for j in range(M):
        if arr[i][j] == 0:
            wall.append([i, j])
        elif arr[i][j] == 2:
            virus.append([i, j])

 

전체 벽 중 3개의 벽을 세워야 하므로, 가능한 조합을 구한다.

wall_list = list(combinations(wall, 3))

 

조합을 모두 돌며 벽을 세우고, bfs를 호출하여 안전 영역의 크기를 계산한다.

이때 원본 리스트(arr)의 값이 변경되는 것을 막기 위해 temp로 값을 복사(copy.deepcopy())하여 사용하였다.

그냥 temp = arr 로 복사하면 같은 주소값을 공유하기 때문에 안 된다.

for i in wall_list:
    temp = copy.deepcopy(arr)
    temp[i[0][0]][i[0][1]] = 1
    temp[i[1][0]][i[1][1]] = 1
    temp[i[2][0]][i[2][1]] = 1

    ans = max(ans, bfs())

 

 

✔️ bfs 함수

 

cnt: 현재 안전 영역의 크기

바이러스의 위치를 deque에 저장한다.

cnt = 0
q = deque()
for j in virus:
    q.append((j[0], j[1]))

새 좌표가 범위 내에 있고, 빈칸이라면 바이러스가 퍼질 것이다.

바이러스가 퍼진 새 좌표를 deque에 추가하여 더 이상 퍼지지 못할 때까지 진행한다.

while q:
    cx, cy = q.popleft()

    for k in range(4):
        nx, ny = cx + dx[k], cy + dy[k]

        if 0 <= nx < N and 0 <= ny < M and temp[nx][ny] == 0:
            temp[nx][ny] = 2
            q.append((nx, ny))

 

변경이 완료된 리스트에서 0의 개수(안전 영역의 크기)를 세어 리턴한다.

for a in range(N):
    cnt += temp[a].count(0)

return cnt

 

 

시간초과를 걱정했는데, 다행히 통과!