17141 - 연구소 2

 

---

 

문제

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

17141번: 연구소 2

 

풀이

 

완전탐색 + Multisource BFS 문제이다. 

여러개의 시작점을 모두 구한 후에, BFS를 모두 실행해본다음, 빈칸에 바이러스를 다 퍼트리는 경우, 최솟값을 구하면 된다. 빈칸에 모두 퍼졌는지는 초기에 빈칸의 개수를 구하고, BFS 실행 로직에 빈칸만큼 바이러스가 퍼진지 확인했다.

 

문제를 풀면서 이슈가 좀 있었는데

 

1. 시간초과

 

처음 완전탐색을 위해서 itertools.permutation 를 사용했다. m이 10정도라 괜찮을 줄 알았는데 여지없이 시간초과가 났다. 재귀를 활용한 dfs로 바꾸어주니 시간초과에서 벗어날 수 있었다.

 

2. 재귀탈출 조건

 

dfs 작성시 탈출조건에 문제가 있었다. m개의 요소를 모두 골랐는지 확인후에, 인덱스 검사를 했어야 했는데 반대로해서 

m과 바이러스 설치 개수(2의 개수)가 같을때 오류가 났다.

 

 

코드

import sys
import copy
from sys import stdin
from collections import deque

# multiple BFS
def bfs(starts):
    global lab, empty, n
    count = 0
    dis = [[0] * n for _ in range(n) ]
    dx = [-1, 1, 0, 0]
    dy = [0, 0, 1, -1]
    # 방문 여부 초기화
    visited = [ [False] * n for _ in range(n)]
    q = deque()

    # 시작점 세팅
    for s in starts:
        a, b = s[0], s[1]
        q.append((a, b))
        visited[a][b] = True
        count += 1

    while q:
        x, y = q.popleft()

        for i in range(4):
            nx = x+dx[i]
            ny = y+dy[i]

            if 0 <= nx < n and 0 <= ny < n :
                # 방문하지 않았고, 벽이 아니라면 거리를 갱신해준다.
                if not visited[nx][ny] and lab[nx][ny] != 1:
                    q.append((nx, ny))
                    dis[nx][ny] = dis[x][y] + 1
                    visited[nx][ny] = True
                    count +=1


    # 빈칸의 개수와, 바이러스 퍼지는 개수가 같으면 모두 퍼진것이다.
    if empty == count:
        return max(map(max, dis))
    else:
        return sys.maxsize


def dfs(vals, idx):
    global s_len, s_points, answer, m
    t_val = copy.deepcopy(vals)

    if len(vals) == m:
        answer = min(answer, bfs(vals))
        return

    if idx >= s_len:
        return

    dfs(vals, idx + 1)
    t_val.append(s_points[idx])
    dfs(t_val, idx + 1)


n, m = map(int, input().split())
lab = [ list(map(int, stdin.readline().rstrip().split())) for _ in range(n) ]
s_points = []
empty = 0
answer = sys.maxsize
for i in range(n):
    for j in range(n):
        if lab[i][j] != 1:
            empty += 1
        if lab[i][j] == 2:
            s_points.append((i, j))

s_len = len(s_points)
dfs([], 0)

if answer == sys.maxsize:
    print(-1)
else:
    print(answer)

 

후기

문제는 정말 단순한데 또 자잘한 실수들이 시간들을 잡아먹는다. 결국 이게 실력이겠지, 꾸준히 연습하자..

그리고 종종 쓰는 메소드들의 시간 복잡도 정도는 파악하고 있자. permutation이나 combination 들 시간 꽤 걸리는건 알고있었는데, 정확히 얼마 걸리는지는 모르니 말이다.