백준 17142 연구소 3 (삼성 기출)

www.acmicpc.net/problem/17142

17142번: 연구소 3

이 문제도 삼성 문제의 유명한 연구소 시리즈 중 하나이다. 이런 격자구조가 나오면 항상 BFS/DFS/DP 등을 생각하게 되는데, 이 문제도 BFS로 풀었다. 다만 조합을 끼얹어야 한다. 

바이러스를 놓을 수 있는 위치들은 맵 상에 표시되어있고, 그 중에서 가장 빠른 확산을 일으킬 수 있는 최적의 M개를 골라야 하는데, 이 M개 선택에 있어 순서는 중요하지 않다. 그래서 순열이 아니라 조합이 된다. 

조합에 대해서는 N과 M문제 시리즈를 풀어보는 것을 추천한다. 그리고 필자의 이전 포스팅을 보는 것도 좋다. 조합을 할 때는 방문체크, 백트래킹 등으로 해결할 수도 있으나, 필자는 파이썬 itertools의 combinations로 구했다. ^^;

 

기본적으로 주어진 바이러스 배치 가능 위치에서 M개를 조합으로 뽑아서

BFS를 돌려보면서 가장 짧은 시간이 걸리는 경우를 찾으면 된다.

 

다만 주의할 부분은 비활성화된 바이러스가 활성화될 때인데, 

활성화되면서 주변에 바로 바이러스를 퍼뜨리는 건 아니다. 그 과정은 다음 시간에 진행된다. 하지만 시간은 계속 가고 있다.(즉, 활성화된 바이러스에 도달한 시간은 기록되어 있어야 한다.) 

그래서 각 칸마다 도달한 시간을 기록하면서 가장 오래 걸린 시간을 찾되, 해당 목표 칸에 비활성 바이러스가 있었다면 그 시간은 포함하지 않는 방식으로 풀이하였다. (아래 코드 참조)

if not board[nxt[0]][nxt[1]]:
	mx = max(mx, cost[nxt[0]][nxt[1]])

위와 같이, 바이러스 전파를 완료한 후에, 해당 칸에 비활성 바이러스가 원래 있었다면, mx갱신을 하지 않는 것이다.

 

<주요 내용>

BFS, 삼성 기출, 구현, 시뮬레이션

 

<코드>

import sys
from collections import deque
from itertools import combinations as cb
si = sys.stdin.readline
 
 
def main():
    n, m = [int(e) for e in si().split()]
    pos, board = [], []
    for i in range(n):
        row = [int(e) for e in si().split()]
        board.append(row)
        for j in range(n):
            if row[j] == 2:
                pos.append((i, j))
 
    def surr(x, y): return [(i, j)for i, j in (
        (x+1, y), (x-1, y), (x, y+1), (x, y-1))if n > i > -1 < j < n]
 
    virus, ret, flag = [i for i in range(len(pos))], 50*50+1, True
    cbs = cb(virus, m)
    for el in cbs:
        t, q, vq, mx = 0, deque(), deque(), 0
        visited = [[False for _ in range(n)]for _ in range(n)]
        cost = [[0 for _ in range(n)]for _ in range(n)]
 
        for e in el:
            visited[pos[e][0]][pos[e][1]] = True
            q.append(pos[e])
 
        def finished(n):
            nonlocal visited, board
            for i in range(n):
                for j in range(n):
                    if board[i][j] != 1 and not visited[i][j]:
                        return False
            return True
 
        while q:
            curr = q.popleft()
            nxts = surr(curr[0], curr[1])
            currcost = cost[curr[0]][curr[1]]
            for nxt in nxts:
                if not visited[nxt[0]][nxt[1]] and board[nxt[0]][nxt[1]] != 1:
                    visited[nxt[0]][nxt[1]] = True
                    cost[nxt[0]][nxt[1]] = 1+currcost
                    q.append(nxt)
                    if not board[nxt[0]][nxt[1]]:
                        mx = max(mx, cost[nxt[0]][nxt[1]])
 
        if not finished(n):
            flag = True and flag
        else:
            flag = False
            ret = min(ret, mx)
    if flag:
        print(-1)
    else:
        print(ret)
 
 
if __name__ == '__main__':
    main()