이번 문제는 삼성 기출 문제로, 재귀를 통해 활성화 바이러스의 combinations를 구하고, combinations를 순회하며 해당 위치에서 바이러스가 퍼지는 과정을 BFS를 이용하여 구현하였다. 바이러스가 퍼지는 시간은 방문처리 리스트에 카운팅하는 방식으로 진행하였는데, 이때 바이러스가 여러곳에서 한번에 퍼지기 때문에 이전에 이미 퍼진 위치인 경우에는 이를 현재 시간 값과 저장된 값 중 최솟값으로 갱신하도록 하였다. 그리고 비활성화 바이러스가 구석에 있을 경우에 비활성화 바이러스까지 퍼지는 시간을 계산하여 예상한 값보다 1이 더 크게 나오는 경우가 있었고 이를 개선하기 위해 최대 시간을 구하는 과정에서 만약 현재 위치의 시간이 이전의 최대 시간보다 클 때에 현재 위치가 바이러스 자리라면 최대 시간을 갱신하지 않도록 하였다.

• n, m을 입력받는다.
• grid를 입력받는다.
• 바이러스들의 위치를 저장할 리스트 viruses를 선언한다.
• n번 반복하는 i에 대한 for문을 돌린다.
  -> n번 반복하는 j에 대한 for문을 돌린다.
  --> 만약 grid[i][j]가 2와 같을 경우,
  ---> viruses에 (i, j)를 넣는다.
• dy, dx에 4 방향을 저장한다.
• combinations를 저장할 리스트 cases를 선언한다.
• get_combs 함수를 cur, result를 인자로 갖도록 선언한다.
  -> 만약 cur이 viruses의 길이와 같을 경우,
  --> 만약 result의 길이가 m과 같을 경우,
  ---> cases에 result를 넣는다.
  --> 함수를 종료한다.
  -> 만약 result의 길이가 m보다 클 경우,
  --> 함수를 종료한다.
  -> get_combs(cur+1, result+[viruses[cur]])를 재귀 호출 한다.
  -> get_combs(cur+1, result)를 재귀 호출 한다.
• bfs함수를 sy, sx를 인자로 갖도록 선언한다.
  -> q를 deque로 선언한다.
  -> q에 (sy, sx)를 넣는다.
  -> visited[sy][sx]를 0으로 갱신한다.
  -> q가 존재하는 동안 반복하는 while문을 돌린다.
  --> y, x를 q의 가장 앞에서 추출한다.
  --> 4번 반복하는 i에 대한 for문을 돌린다.
  ---> ny, nx를 y+dy[i], x+dx[i]로 선언한다.
  ---> 만약 ny, nx가 0 이상, n 미만이고, grid[ny][nx]가 1이 아니고, visited[ny][nx]이 -1이거나 visited[y][x]+1보다 클 경우,
  ----> visited[ny][nx]를 visited[y][x]+1로 갱신한다.
  ----> q에 (ny, nx)를 넣는다.
• get_combs(0, [])를 호출한다.
• 결과를 저장할 변수 answer를 sys.maxsize로 선언한다.
• cases를 순회하는 case에 대한 for문을 돌린다.
  -> 방문 처리와 카운팅에 사용할 리스트 visited를 n*n의 크기로 선언하고, -1로 채운다.
  -> case를 순회하는 y, x에 대한 for문을 돌린다.
  --> bfs(y, x)를 호출한다.
  -> case에서의 최댓값을 저장할 변수 ans를 0으로 선언한다.
  -> 전체 방문이 가능한지 여부를 체크할 변수 chk를 True로 선언한다.
  -> n번 반복하는 i에 대한 for문을 돌린다.
  --> n번 반복하는 j에 대한 for문을 돌린다.
  ---> 만약 visited[i][j]가 -1이고, grid[i][j]가 0일 경우,
  ----> chk를 False로 갱신한다.
  ----> 반복문을 종료한다.
  ---> 만약 ans가 visited[i][j]보다 작고, grid[i][j]가 2가 아닐 경우,
  ----> ans를 visited[i][j]로 갱신한다.
  --> 만약 chk가 False일 경우,
  ---> 반복문을 종료한다.
  -> 만약 chk가 True일 경우,
  --> answer를 ans와 answer 중의 최솟값으로 갱신한다.
• 만약 answer가 sys.maxsize일 경우,
  -> answer를 -1로 갱신한다.
• answer를 출력한다.

Code

import sys
from collections import deque
input=sys.stdin.readline
n, m=map(int, input().split())
grid=[list(map(int, input().split())) for _ in range(n)]
viruses=[]
for i in range(n):
    for j in range(n):
        if grid[i][j]==2:
            viruses.append((i, j))
dy, dx=[0, 1, 0, -1], [1, 0, -1, 0]
cases=[]
def get_combs(cur, result):
    if cur==len(viruses):
        if len(result)==m:
            cases.append(result)
        return
    if len(result)>m:
        return
    get_combs(cur+1, result+[viruses[cur]])
    get_combs(cur+1, result)
def bfs(sy, sx):
    q=deque()
    q.append((sy, sx))
    visited[sy][sx]=0
    while q:
        y, x=q.popleft()
        for i in range(4):
            ny, nx=y+dy[i], x+dx[i]
            if 0<=ny<n and 0<=nx<n and grid[ny][nx]!=1  and (visited[ny][nx]==-1 or visited[ny][nx]>visited[y][x]+1):
                visited[ny][nx]=visited[y][x]+1
                q.append((ny, nx))
get_combs(0, [])
answer=sys.maxsize
for case in cases:
    visited = [[-1 for _ in range(n)] for _ in range(n)]
    for y, x in case:
        bfs(y, x)
    ans=0
    chk=True
    for i in range(n):
        for j in range(n):
            if visited[i][j]==-1 and grid[i][j]==0:
                chk=False
                break
            elif ans<visited[i][j] and grid[i][j]!=2:
                ans=visited[i][j]
        if not chk:
            break
    if chk:
        answer=min(ans, answer)
if answer==sys.maxsize:
    answer=-1
print(answer)