[221009] 백준 17142 : 연구소 3

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

17142번: 연구소 3

1. 핵심 포인트 두 가지

 본 문제는 전형적인 브루트 포스(완전 탐색) + BFS(or DFS) 알고리즘이다. 이번 문제를 풀면서 고려할 핵심 포인트 두 가지는 다음과 같다.

1. 모든 경우의 수에 대해 탐색해야 한다.
2. 동시에 움직이면서 시간 체크도 해주어야 한다. 

 모든 경우의 수는 어떻게 탐색할까? 백트래킹, DFS 등 방법이 많다. 나는 여기에서 순열(combination) 함수를 택했다.

(활성시킬 바이러스의 순서는 중요하지 않다.) 소스코드 예제는 다음과 같다.

def combination(arr, t):
    result = []
    if t == 0 : return [[]]
    for i in range(len(arr)):
        elem = arr[i]
        rest_arr = arr[i + 1 : ]
        for C in combination(rest_arr, t - 1):
            result += [[elem] + C]
    return result

 다음엔 움직이면서 시간 체크해주는 것이다. 총 3가지를 고려해서 짜면 된다.

• 빈칸이 몇 개 남았는가(없다면 빠져나올 수 있도록 한다.)
• 동일 시간 동안에 한 번에 움직이자.(큐에 넣은 만큼 같은 시간에 존재하는 것들은 전부 실행시킨다.)
• 빈칸이 존재하지만 큐에 넣을 것이 더 이상 없다.(나온다)

특히 두 번째 같은 조건의 경우 불, 탈출 문제 풀었을 때와 비슷한 상황이다. 여러 개의 포인트들이 동시에 일어날 때에는 3중 반복문으로 해결해주어야 한다. 이때, 항상 계산 시간이 타당한지 예측을 해보자. 내 기억으로는 파이썬 기준으로 100만 번 계산 시 1초가 걸리는 것으로 알고 있다.  

 

2. 전체 코드

 메모리 : 116160 KB, 시간 : 228 ms, 풀이 시간 : 90 + a

N, M = map(int, input().split())
board = [list(map(int, input().split())) for _ in range(N)]
info = []
empty_cnt = 0
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
for i in range(N):
    for j in range(N):
        if board[i][j] == 2 :
            info.append([i, j])
        if board[i][j] == 0 :
            empty_cnt += 1

def combination(arr, t):
    result = []
    if t == 0 : return [[]]
    for i in range(len(arr)):
        elem = arr[i]
        rest_arr = arr[i + 1 : ]
        for C in combination(rest_arr, t-1):
            result.append([elem] + C)
    return result

def bfs():
    res = 1e9
    comb = combination(info, M)
    for temp in comb :
        q = temp
        visited = [[False for _ in range(N)] for _ in range(N)]
        for x, y in temp :
            visited[x][y] = True
        time = 0
        num_zero = empty_cnt
        while True :
            size = len(q)
            if size == 0 or num_zero == 0 :
                if num_zero == 0 :
                    break
                else :
                    time = 1e9
                    break
            time += 1
            for _ in range(size):
                x, y = q[0]
                del q[0]
                for d in range(4):
                    nx = x + dx[d]
                    ny = y + dy[d]
                    if 0 <= nx < N and 0 <= ny < N :
                        if not visited[nx][ny] :
                            if board[nx][ny] == 2 : # 감염은 동시다발적
                                q.append([nx, ny])
                                visited[nx][ny] = True
                            elif board[nx][ny] == 0 :
                                visited[nx][ny] = True
                                q.append([nx, ny])
                                num_zero -= 1
        res = min(res, time)

    if res == 1e9 : print(-1)
    else : print(res)

bfs()