새소식

인기 검색어

Algorithm/Python

[백준] 14502 연구소(BFS) - Python

  • -
 

14502번: 연구소

인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크

www.acmicpc.net

 

- 문제 설명

  • 연구실에서 바이러스가 유출되었는데 바이러스가 퍼지기 전에 3개의 벽을 세워 바이러스의 침입을 막는다.
  • 바이러스가 가장 적게 퍼지도록 했을 경우의 안전구역 갯수를 반환해보자

- 접근 방법

  • 바이러스가 없는 입력이 0인 구역에서 3개를 뽑아 벽을 세우는 모든 경우의 수를 구한다.
  • 경우의 수마다 3개의 벽을 세웠을 때 안전구역의 개수를 구해 최댓값을 구한다.

 

- 입출력 예시

- 코드

from itertools import combinations
from collections import deque
from copy import deepcopy
# 바이러스가 있는곳 4방향 탐색
dr = [-1, 1, 0, 0]
dc = [0, 0, -1, 1]
# 유효한 범위인지 검사
def is_valid(r, c):
    return 0 <= r < n and 0 <= c < m

def BFS():
    safe_max = 0    # 안전구역이 가장 많을 때 안전구역의 수
    # 바이러스 없는 구역 3곳을 뽑는 경우의 수만큼 반복
    for i in safe:
        for j in i:             # 바이러스 없는 구역 3곳에 벽 설치
            v_lab[j[0]][j[1]] = 1
        v_q = deepcopy(q)       # 반복마다 큐, 실험실 초기상태로 갱신
        v_lab = deepcopy(lab)
        
        while v_q:      # 큐가 비어있을 때까지 반복
            r, c = v_q.popleft()    # 바이러스가 있는 구역 pop
            for d in range(4):
                nr = r + dr[d]
                nc = c + dc[d]
                # 네방향 탐색해서 벽이 아니고 바이러스가 없을경우 바이러스 감염
                if is_valid(nr, nc) and v_lab[nr][nc] == 0:
                    v_lab[nr][nc] = 2
                    v_q.append((nr, nc))    # 감염시킨 구역을 큐에 추가
        
        # 감염이 끝난 실험실에서 안전구역을 세어 최댓값 갱신          
        safezone = 0
        for i in v_lab:
            safezone += i.count(0)
        if safe_max < safezone:
            safe_max = safezone
    return safe_max

n, m = map(int, input().split())
lab = [list(map(int, input().split())) for _ in range(n)]   # 연구소 지도 입력
safe = []

for i in range(n):
    for j in range(m):
        if lab[i][j] == 0:
            safe.append((i, j))
# 바이러스가 없는 구역 3개를 뽑아 벽을 세우는 모든 경우의 수
safe = list(combinations(safe, 3))      # 조합 이용

q = deque()
# 바이러스가 있는 지역 모두 큐에 추가
for i in range(n):
    for j in range(m):
        if lab[i][j] == 2:
            q.append((i, j))

print(BFS())

 

코드가 너무 길어진거 같지만 한번에 성공했다ㅎㅎ

Contents

포스팅 주소를 복사했습니다

이 글이 도움이 되었다면 공감 부탁드립니다.