[BOJ] 17142번 연구소 3 (Python) [삼성 SW 역량 테스트 기출 문제] - 중요

문제

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

풀이

시간초과로 애를 먹었다. deepcopy를 쓰지 않게 하고, 복사하는 부분을 최대한 빼도 시간초과가 났다.

시간복잡도를 잘못 파악했고, BFS를 쓰게되면 1초가 흘렀을때의 이동만을 체크하기 어렵다고 생각했는데 잘못 생각했다.

BFS로 특정위치에 도달할때까지 최소 몇 초가 걸렸는지 알 수 있다. 이 값이 N인 값들이 N초에 도달한 곳들이다.

BFS로 접근하지 않아서 시간초과가 난거다!

BFS에서 몇 초가 흘렀는지를 함께 체크할 수 있고, 이렇게 해야 시간복잡도가 확 준다.

기존에 빈칸(0)이 없어질때까지 for문을 돌며 모든 활성화된 virus들에 대해 for문을 도는건
$O(N^2) * O(N^2)$로 $O(N^4)$이 된다. 물론 N^4보다는 작겠지만 시간복잡도가 매우 높다. 조합 경우의 수까지 있으므로 252*50*50*50*50 = 1,575,000,000 (10억)으로 터지는게 맞았다.

이후에 BFS로 다시 풀었다. 비활성 바이러스 처리가 까다로웠는데,

• 비활성 바이러스 => 활성 바이러스
• 빈 곳 => 활성 바이러스

2가지 경우에 대해 후자만 second를 갱신하도록 코드를 짰다.

+) float('inf')를 == 연산해도 잘된다.

import sys
from itertools import combinations
from collections import deque

EMPTY, WALL, INACTIVE_VIRUS, ACTIVE_VIRUS = 0, 1, 2, 3
DX_DY = [(1, 0), (-1, 0), (0, 1), (0, -1)]  # 상하좌우

input = sys.stdin.readline


def is_valid(x, y, graph, visited):
    """확산 대상인지 체크"""
    if 0 <= x < N and 0 <= y < N \
      and graph[x][y] in [EMPTY, INACTIVE_VIRUS] \
      and not visited[x][y]:
        return True
    return False


def bfs(graph, active_viruses, visited):
    queue = deque([])

    for x, y in active_viruses:
        visited[x][y] = True
        queue.append((x, y, 0))

    total_sec = 0
    while queue:
        x, y, sec = queue.popleft()

        if graph[x][y] == EMPTY: # 비활성-> 활성은 갱신X
          total_sec = max(total_sec, sec)
      
        for dx, dy in DX_DY:
            new_x, new_y = x + dx, y + dy
            if is_valid(new_x, new_y, graph, visited):
                visited[new_x][new_y] = True
                queue.append((new_x, new_y, sec + 1))
              
    return total_sec


N, M = map(int, input().split())
graph = [list(map(int, input().split())) for _ in range(N)]

all_virus_xy = []
for i in range(N):
    for j in range(N):
        if graph[i][j] == INACTIVE_VIRUS:
            all_virus_xy.append((i, j))

ans = float('inf')
virus_combinations = map(list, combinations(all_virus_xy, M))
for active_viruses in virus_combinations:
    copied_graph = [l[:] for l in graph]  # 원복 복제
    for x, y in active_viruses:
        copied_graph[x][y] = ACTIVE_VIRUS  # 활성화된 곳 표시

    visited = [[False] * N for _ in range(N)]  # 방문한곳체크
    total_sec = bfs(copied_graph, active_viruses, visited) # 확산할수있는만큼한 시간

    impossible = False
    for i in range(N):
      for j in range(N):
        if is_valid(i,j,copied_graph, visited): # 확산되어야 하는데 안된 곳 있으면
          impossible = True
          
    if not impossible:
      ans = min(ans, total_sec)
      
          
# ans가 float('inf')면 -1 프린트 아니면 ans 출력
if ans == float('inf'):
    print(-1)
else:
    print(ans)