[백준] G5. boj14502 연구실 / 분류: bfs 🙁

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

14502번: 연구소

import sys
import copy
from itertools import combinations
from collections import deque

N, M = map(int, sys.stdin.readline().split())

#전체 graph, 0의 인덱스들, 바이러스가 있는 인덱스들
graph = []
zeros = []
viruses = []
for i in range(N):
    row = list(map(int, sys.stdin.readline().split()))
    graph.append(row)
    for j, x in enumerate(row):
        if x == 0:
            zeros.append((i,j))
        elif x == 2:
            viruses.append((i,j))
#zeros에 있는 인덱스들 3개씩 조합 만들기
zeros_combi = list(combinations(zeros, 3))

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

result = 0
temp = []
for c in zeros_combi:
	#deepcopy 이용해서 graph 복사
    temp = copy.deepcopy(graph)
    cnt = 0
    for wall in c: #벽 세우기
        temp[wall[0]][wall[1]] = 1
    #큐에 바이러스 위치한 배열들 넣고 bfs로 바이러스 퍼뜨리기
    queue = deque(viruses)
    while queue:
        x, y = queue.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < N and 0 <= ny < M and temp[nx][ny] == 0:
                temp[nx][ny] = 2
                queue.append((nx,ny))
    #안전구역 세기
    for row in temp:
        for val in row:
            if val == 0:
                cnt += 1
    result = max(result, cnt)

print(result)

 

• combinations를 이용해서 조합을 만들 수 있다.
• deepcopy를 이용해서 배열을 복사할 수 있다. 그냥 할당으로 하면 복사가 아니라 같은 곳을 가리킨다.