[백준-골드4] 17142번 연구소 3(BFS, 파이썬)

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

17142번: 연구소 3

 

<내 코드>

[틀렸던 이유]

- 활성화 바이러스 m개를 선택하면 비활성화 바이러스가 있다. bfs를 탐색하면서 이 부분을 고려하는게 어려웠다.

- 비활성화 바이러스(2)는 지나갈수있다. 즉, 큐에 담을 수 있고, 이 때마다 거리가 증가 되어 오답을 유발한다.

- 비활성화 바이러스가 마지막 경로(경계)에 있는 경우 거리가 정답보다 1크게 코드가 작동했었다.

- 그래서 빈칸일때만 bfs를 동작시켰었는데 이래도 틀린다,,, 

- 따라서 max_dist 변수를 이용해 그래프가 0인 경우에 최대 거리를 계속 업데이트해서 저장해줬다.

 

 

- 우선 처음으로 입력을 받고, is_full 변수를 통해 처음부터 빈칸없이 바이러스가 전파된 경우를 파악하고, 

  바이러스 위치 좌표를 따로 리스트에 담았다.

- combinations를 사용해서 활성화될 m개의 바이러스를 선택하는 조합의 리스트를 생성했다.

- bfs 함수에서는 미리 큐에 선택된 m개의 좌표를 담아두고 시작했다.

- 벽인 경우를 제외하고 상하좌우로 탐색하며 거리를 하나씩 늘려서 파악한다.

- 이 때 비활성바이러스를 고려하기위해 빈칸인경우에만 max_dist 변수에 현재 거리를 업데이트해주었다.

- 그리고 바이러스가 전파가 다 되었는지 확인하기위해 이동한 곳은 2로 바꾸어 바이러스 전파 처리했다.

- flag 변수는 모든 영역에 바이러스가 전파되었는지 확인하는 변수이다.

- flag가 True일 경우에만 result에 거리를 담는다.

 

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

# 입력
n, m = map(int, sys.stdin.readline().split())
graph = []
for _ in range(n):
    graph.append(list(map(int, sys.stdin.readline().split())))

# 바이러스 좌표 담기
#처음부터 바이러스만 있는경우
is_full = True
virus = []
for i in range(n):
    for j in range(n):
        if graph[i][j] == 2:
            virus.append([i, j])
        if graph[i][j] == 0:
            is_full = False

# m개 활성화될 바이러스 고르는 경우의 수
virus_list = list(combinations(virus, m))
dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]

def bfs():
    max_dist = 0
    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 < n:
                if copy_graph[nx][ny] != 1 and dist[nx][ny]==-1:
                    dist[nx][ny] = dist[x][y] + 1 #거리 증가
                    # 빈칸인 경우 현재 거리를 저장
                    # 이 부분을 고려안해서 몇시간 고생함 ㅜ
                    if copy_graph[nx][ny]==0:
                        max_dist = max(max_dist, dist[nx][ny])
                    queue.append([nx, ny])
                    copy_graph[nx][ny] = 2 #바이러스 전파

    # 모든 영역에 바이러스가 다 퍼졌는지 체크
    flag = True
    for i in range(n):
        if 0 in copy_graph[i]:
            flag = False
    if flag==True:
        result.append(max_dist)

result = []
for v in virus_list:
    # 활성 바이러스 큐에 담기
    copy_graph = copy.deepcopy(graph)
    queue = deque()
    dist = [[-1] * n for _ in range(n)]  # 최소거리(시간) 담을 리스트
    for a, b in v:
        queue.append([a, b])
        dist[a][b] =0

    bfs()

if result:
    if is_full: #처음부터 벽을 제외한 공간에 바이러스가 전파된 경우
        print(0)
    else:
        print(min(result))
else:# 모든 공간에 바이러스 전파에 실패한 경우
    print(-1)