파이썬)연구소2 -BOJ

 

 

from itertools import combinations
from collections import deque
from copy import deepcopy
import sys
input = sys.stdin.readline

n, m = map(int, input().split())

arr = []
vi = []

for i in range(n):
    l = list(map(int, input().split()))
    arr.append(l)
    for j in range(len(l)):
        if l[j] == 2:
            vi.append([i, j])
result = float('inf')

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


def bfs(vir):
    q = deque()
    cnt = 0
    visit = [[-1 for _ in range(n)]for _ in range(n)]

    for v in vir:
        q.append((v[0], v[1]))
        visit[v[0]][v[1]] = 0

    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 visit[nx][ny] == -1 and arr[nx][ny] != 1:
                    q.append((nx, ny))
                    visit[nx][ny] = visit[x][y] + 1
                    cnt = max(cnt, visit[nx][ny])

    for i in range(len(visit)):
        for j in range(len(visit[0])):
            if visit[i][j] == -1 and arr[i][j] != 1:
                return 10000
    return cnt


for virus in combinations(vi, m):
    result = min(result, bfs(virus))

if result > 1000:
    print(-1)
else:
    print(result)

해당 문제는 BFS를 이용한 완전탐색 유형이다.

우선 고려해야 할 점이 한가지 있다.

• m개의 바이스러를 중복되지 않게 어떻게 설치할 것인가

이다.

해당 방법은 n의 개수 (1 <= n < 50)을 보곤 완전탐색을 이용해도 시간 복잡도가 딱 떨어지겠다 싶어서 사용했다.

Itertools의 cominations는 어떤 리스트의 조합을 반환한다.

해당 코드에서는 arr을 돌며 2가 있는 자리(i,j)를 기억한 후 조합으로 선별했다.

그 다음은 일반적인 BFS알고리즘과 같다.