백준 14502 : 연구소 (by python) - BFS, 조합

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

 

아이디어

연구소의 최대 크기가 크지 않기 때문에 벽을 세우는 모든 경우의 수를 파이썬의 combination(조합)을 이용해 탐색하면된다.

1. 입력받은 연구소에서 빈칸의 좌표와 바이러스의 좌표를 각각 저장한다.
2. 빈칸의 좌표 중에서 Combinations를 사용하여 3개를 조합해 탐색한다.
   1. 해당 조합의 좌표에 벽을 세우고 바이러스를 최대로 확장한다.
   2. 연구소의 남은 안전구역을 계산한다.
3. 남은 안전구역이 최대가 되는 값을 출력한다.

 

바이러스 확산

이때 연구소의 바이러스를 확장할 때에는 BFS를 사용하여 확장하였다.

def bfs(temp_graph):
    q = deque(virus_positions) 
    while q:
        x, y = q.popleft()
        for i in range(4): 
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < n and 0 <= ny < m and temp_graph[nx][ny] == 0:
                temp_graph[nx][ny] 
                q.append((nx, ny))

 

일반적인 BFS로 모든 바이러스위치에 대해 뻗어나갈 수 있는 경로에 바이러스를 감염시킨다.

 

 

안전구역 계산

def safe_zone(temp_graph):
    count = 0
    for i in range(n):
        safe_zone += temp_graph[i].count(0) 
    return count

 

 

코드

from collections import deque
from itertools import combinations

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

n, m = map(int, input().split())
graph = [list(map(int, input().split())) for _ in range(n)]
empty_spaces = []
virus_positions = []

for i in range(n):
    for j in range(m):
        if graph[i][j] == 0:
            empty_spaces.append((i, j)) 
        elif graph[i][j] == 2:
            virus_positions.append((i, j)) 

def bfs(temp_graph):
    q = deque(virus_positions)  
    while q:
        x, y = q.popleft()
        for i in range(4):  
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < n and 0 <= ny < m and temp_graph[nx][ny] == 0:
                temp_graph[nx][ny] = 2  
                q.append((nx, ny))

def safe_zone(temp_graph):
    count = 0
    for i in range(n):
        safe_zone += temp_graph[i].count(0)  
    return count

# 벽 3개를 세우는 모든 조합에 대해 시뮬레이션 실행
result = 0
for walls in combinations(empty_spaces, 3):
    temp_graph = [row[:] for row in graph]  # 원본 그래프 깊은 복사

    # 선택된 3개의 빈 칸에 벽을 세우기
    for wx, wy in walls:
        temp_graph[wx][wy] = 1

    # 바이러스 확산
    bfs(temp_graph)

    # 안전 구역 계산
    result = max(result, safe_zone(temp_graph))

print(result)