[BOJ 백준] 17141번 : 연구소 2

 

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

17141번: 연구소 2

 

이 문제는 조합(combinations)을 사용해서 풀어야 하는 문제였다.

 

그러나 나는 써본 적이 없어서 이걸 어떻게 풀어야 하나 1시간 가량 고민하다가 풀이를 참고해서 풀었다.

 

자세한 설명은 코드에 주석을 달아놨으니 참고하면 된다.

 

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

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

res = float("inf")

def bfs(v): # v는 combination 한줄씩 입력받음
    queue = deque(v)
    visited = [[-1] * N for _ in range(N)]
    m = 0 # 최소 횟수를 찾기 위한 변수    
    for x, y in queue:
        visited[x][y] = 0

    while queue:
        a, b = queue.popleft()
        for i in range(4):
            nx = a + dx[i]
            ny = b + dy[i]
            if 0 <= nx < N and 0 <= ny < N:
                if graph[nx][ny] != 1 and visited[nx][ny] == -1:
                    queue.append((nx, ny))
                    visited[nx][ny] = visited[a][b] + 1
                    m = max(m, visited[a][b] + 1)
                    

    # bfs가 끝난 이후 바이러스에 감염되지 않은 빈 칸이 있다면 감염시킬수 없는 경우
    # 따라서 inf를 리턴해줌
    for i in range(N):
        for j in range(N):
            if visited[i][j] == -1 and graph[i][j] != 1:
                return res

    return m



N, M = map(int, input().split())

graph = []
virus = []
for x in range(N):
    graph.append(list(map(int, input().split())))

for i in range(N):
    for j in range(N):
        if graph[i][j] == 2:
            virus.append((i, j))

# 바이러스의 좌표들 중 M개를 뽑은 모든 경우에 대해서 bfs 수행하며 최솟값 갱신
for v in combinations(virus, M):
    res = min(bfs(v), res)

# 탐색하지 못하는 경우 answer에는 inf값이 들어있다
if res == float("inf"):
    print(-1)
else : 
    print(res)