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

---

1. 코드

from itertools import combinations
from collections import deque

dx = [-1, 1, 0, 0]
dy = [0, 0, 1, -1]

ans = 99999
N, M = map(int, input().split())
og_graph = [list(map(int, input().split())) for _ in range(N)]
lst = []
for i in range(N):
    for j in range(N):
        if og_graph[i][j] == 2:
            lst.append((i, j))

for case in list(combinations(lst, M)):
    q = deque(case)
    graph = [[0] * N for _ in range(N)]
    start_pos = set(list(case))
    
    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 og_graph[nx][ny] != 1 and graph[nx][ny] == 0 and (nx, ny) not in start_pos:
                    graph[nx][ny] = graph[x][y] + 1
                    q.append((nx, ny))
    for x, y in case:
        graph[x][y] = 0

    max_value = -1
    zero_cnt = 0
    for i in range(N):
        for j in range(N):
            if og_graph[i][j] != 1:
                if graph[i][j] == 0:
                    zero_cnt += 1
                max_value = max(max_value, graph[i][j])

    if zero_cnt == M:
        ans = min(ans, max_value)

if ans == 99999:
    print(-1)
else:
    print(ans)

"""
반례1
5 2
1 1 1 1 1
1 1 2 1 1
1 1 2 1 1
1 1 1 1 1
1 1 1 1 1

반례2
5 2
2 2 1 1 1
0 0 1 1 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
"""

---

2. 후기

방문을 나타내는 별도의 2차원 배열을 사용하지 않고 풀었다.

반례2: 시작지점에서 또다른 시작지점으로 +=1 연산이 수행되서 오답처리

-> 바이러스 시작 지점으로 선택받은 2 좌표들을 start_pos 집합안에 넣어서 매 조건문마다 탐색 좌표가 시작점인지를 검사하는 로직을 사용했다.