[백준] 17142번: 연구소 3

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

17142번: 연구소 3

활성화 할 바이러스를 조합으로 brute force해서 최소시간을 구해야겠다 

라고 풀이는 간단하게 떠올릴 수 있었으나 시간초과로 삽질 + 최소 시간 카운트 방법으로 삽질을 했다. 

쉬운줄 알았으나 ???? 이렇게 삽질을 많이 할줄 몰랐다 정확하고 빠르게 푸는 연습을 더 많이 해야겠다.. 

시간초과 코드 

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

input = sys.stdin.readline

n, m = map(int, input().split())

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

# 모든 빈칸에 바이러스 있는지 체크
def check(new_array):
    for i in range(n):
        for j in range(n):
            if new_array[i][j] == 0:
                return False
    return True

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

answer = int(1e9) # 총 소요 시간
flag = False
def bfs(v):
    global answer, flag
    count = 0
    queue = deque(v)
    queue.append((-1, -1))
    new_array = copy.deepcopy(array)
    count = 1

    while queue:
        if check(new_array):
            flag = True
            answer = min(answer, count)
            return
        x, y = queue.popleft()

        if x == -1 and y == -1:
            count += 1
            if len(queue) > 0: # 아직 큐에 원소가 남아있으면 체크용 값 큐에 넣기 , 아니면 종료
                queue.append((-1, -1))
            continue

        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < n and 0 <= ny < n and new_array[nx][ny] != 1:
                if new_array[nx][ny] == 0:
                    new_array[nx][ny] = 3
                    queue.append((nx, ny))
                if new_array[nx][ny] == 2:
                    new_array[nx][ny] = 3
                    queue.append((nx, ny))

if check(array):
    print(0)
else:
    for combi in combinations(virus_info, m):
        bfs(list(combi))

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

 

정답코드 

deepcopy를 빼주었고, 벽을 제외한 모든칸이 바이러스인지 체크를 한번만 해주도록 바꾸었다. 

그리고 queue에다가 1초가 지났다 의미로 넣어준 (-1, -1) 대신 visited를 이용하여 시간을 체크해주었다. 

단순하게 (-1, -1) 를 넣어주는건 정확하지 않다 !! queue에 배열 범위를 초과하는 값들이 들어가도 필터링이 안되서 잘못 카운트 할 수 도 있기 때문이다.. 

from collections import deque
from itertools import combinations
import sys

input = sys.stdin.readline

n, m = map(int, input().split())

array = []
virus_info = []
wall = 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_info.append((i, j))
        elif data[j] == 1:
            wall += 1

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


def bfs(v):
    queue = deque()
    visited = [[-1] * n for _ in range(n)]
    for a, b in v:
        queue.append((a, b))
        visited[a][b] = 0
    # queue.append((-1, -1))

    time = 0

    while queue:
        x, y = queue.popleft()
        # if x == -1 and y == -1:
        #     time += 1
        #     if len(queue) > 0: # 아직 큐에 원소가 남아있으면 체크용 값 큐에 넣기 , 아니면 종료
        #         queue.append((-1, -1))
        #
        #     continue

        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < n and 0 <= ny < n and visited[nx][ny] == -1:
                if array[nx][ny] == 0:
                    queue.append((nx, ny))
                    visited[nx][ny] = visited[x][y] + 1
                    time = max(time, visited[nx][ny])
                elif array[nx][ny] == 2:
                    queue.append((nx, ny))
                    visited[nx][ny] = visited[x][y] + 1

    check = 0
    for row in visited:
        check += row.count(-1)
    if check == wall:
        return time
    else:
        return int(1e9)


answer = int(1e9) # 총 소요 시간

for combi in combinations(virus_info, m):
    answer = min(bfs(list(combi)), answer)

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