[백준] 17142번 - 연구소 3 (Python/파이썬)

예전에 풀었었는데, 재채점 이후에 틀렸다고 그래서 다시 풀게 되었다. 

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

17142번: 연구소 3

1차 시도 

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

import sys
from collections import deque
from itertools import combinations
input = sys.stdin.readline

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

n, m = map(int, input().split())
array = []
answer = int(1e9) # 총 소요 시간
wall = 0 # 벽의 개수
virus_pos = [] # 2 번 좌표값

for i in range(n):
    data = list(map(int, input().split()))
    array.append(data)
    for j in range(n):
        if data[j] == 2:
            virus_pos.append([i, j])
        elif data[j] == 1:
            wall += 1

def bfs(v_list):
    visited = [[-1] * n for _ in range(n)]
    queue = deque([])
    for i in range(m):
        queue.append([v_list[i][0], v_list[i][1]])
        visited[v_list[i][0]][v_list[i][1]] += 1
    time = 0
    while queue:
        x, y = queue.popleft()
        for i in range(4):
            nx, ny = x + dx[i], y + dy[i]
            if 0 <= nx < n and 0 <= ny < n and visited[nx][ny] == -1: # not visited
                if array[nx][ny] == 0: # 빈칸
                    visited[nx][ny] = visited[x][y] + 1
                    queue.append([nx, ny])
                    time = max(time, visited[nx][ny])
                elif array[nx][ny] == 2: # virus
                    visited[nx][ny] = visited[x][y] + 1
                    queue.append([nx, ny])

    # check
    check = 0
    for i in range(n):
        check += visited[i].count(-1)
    if check == wall:
        return time
    else:
        return int(1e9)

for comb in combinations(virus_pos, m):
    result = bfs(comb)
    answer = min(result, answer)

if answer == int(1e9):
    print(-1)
else:
    print(answer)

98% 에서 틀림 

반례 

4 1
2 1 1 2
1 1 1 1
1 1 1 1
2 1 1 2
-1

여기서 -1 이 아니라 0이 나와야 된다. 모든 빈칸에 바이러스를 퍼뜨리면 되는건데 이미 빈칸이 없으므로 정답처리해버리면 되기 때문이다.. 

빈칸이 0개 일때 바로 0출력하고 바로 종료시키는 예외처리를 추가했다. 

import sys
from collections import deque
from itertools import combinations
input = sys.stdin.readline

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

n, m = map(int, input().split())
array = []

INF = int(1e9)
answer = INF # 총 소요 시간
wall = 0 # 벽의 개수
virus_pos = [] # 2 번 좌표값
empty = 0 # 빈칸
for i in range(n):
    data = list(map(int, input().split()))
    array.append(data)
    for j in range(n):
        if data[j] == 2:
            virus_pos.append((i, j))
        elif data[j] == 1:
            wall += 1
        else:
            empty += 1
if empty == 0:
    print(0)
    exit(0)

def bfs(v_list):
    visited = [[-1] * n for _ in range(n)]
    queue = deque([])
    for i in range(m):
        queue.append([v_list[i][0], v_list[i][1]])
        visited[v_list[i][0]][v_list[i][1]] = 0
    time = 0
    while queue:
        x, y = queue.popleft()
        for i in range(4):
            nx, ny = x + dx[i], y + dy[i]
            if 0 <= nx < n and 0 <= ny < n and visited[nx][ny] == -1: # not visited
                if array[nx][ny] == 0: # 빈칸
                    visited[nx][ny] = visited[x][y] + 1
                    queue.append([nx, ny])
                    time = max(time, visited[nx][ny])
                elif array[nx][ny] == 2: # virus
                    visited[nx][ny] = visited[x][y] + 1
                    queue.append([nx, ny])

    # check
    check = 0
    for i in range(n):
        check += visited[i].count(-1)
    if check == wall:
        return time
    else:
        return INF

for comb in combinations(virus_pos, m):
    answer = min(bfs(comb), answer)

if answer != INF:
    print(answer)
else:
    print(-1)

이틀 고민끝에 해결 ..!!