문제

https://www.acmicpc.net/problem/17141
저번에 풀이한 개리맨더링과 유사한 문제이다.
참고: 개리맨더링

풀이

먼저 바이러스가 위치 할 수 있는 조합들을 구해 바이러스의 시작위치를 정하고 bfs를 통해 탐색해서 이동한 거리의 정보를 구한다.

각 탐색의 최장 이동 거리 중 최소 거리를 비교를 통해 구하여 출력하면된다.

어떠한 경우에도 바이러스가 모두 퍼지지 않는다면 -1을 출력해주면 된다.

CODE

import sys
from collections import deque

input = sys.stdin.readline
sys.setrecursionlimit(10 ** 8)
ans = 2505


def solve():
    global ans
    n, m = map(int, input().split())
    lab = [list(map(int, input().split())) for _ in range(n)]
    dr = [0, 0, -1, 1]
    dc = [-1, 1, 0, 0]
    
    # 바이러스의 위치 정보를 리스트로 만들기
    def get_virus_loc_list(arr):
        virus_list = []
        rows, cols = len(arr), len(arr[0])

        for i in range(rows):
            for j in range(cols):
                if arr[i][j] == 2:
                    virus_list.append([i, j])

        return virus_list

    def is_over(r, c):
        if r < 0 or c < 0 or r >= n or c >= n:
            return True
        else:
            return False
        
    # bfs를 통해 그래프 탐색
    def bfs(v_list):
        q = deque([])
        dist = [[-1 for _ in range(n)] for _ in range(n)]
        max_dist = 0
        
        # 바이러스의 초기위치를 큐에 push 하고 초기 위치의 거리를 0으로 초기화
        for loc in v_list:
            q.append(loc)
            dist[loc[0]][loc[1]] = 0
    
        while q:
            now = q.popleft()
            r, c = now[0], now[1]
            max_dist = max(dist[r][c], max_dist)

            for i in range(4):
                nr, nc = r + dr[i], c + dc[i]
                
                # 범위를 넘어서거나 이미 방문한 곳이면 continue
                if is_over(nr, nc) or dist[nr][nc] != -1:
                    continue
                
                # 벽이면 continue
                if lab[nr][nc] == 1:
                    continue

                dist[nr][nc] = dist[r][c] + 1
                q.append([nr, nc])
        
        # 만일 탐색하지 못한 곳이 발생했을 경우 2505 return
        for i in range(n):
            for j in range(n):
                if dist[i][j] == -1 and lab[i][j] != 1:
                    return 2505

        return max_dist

    virus_locs = get_virus_loc_list(lab)

    # 바이러스 m개 고르기
    def select_virus(now, selected, v_list):
        global ans
        if selected == m:
            if not len(v_list):
                return
            ans = min(bfs(v_list), ans)
            return

        if now >= len(virus_locs):
            return

        select_virus(now + 1, selected, v_list)
        select_virus(now + 1, selected + 1, v_list + [virus_locs[now]])

    select_virus(0, 0, [])
    
    # 모든 경우가 탐색하지 못하는 곳이 있다면 -1 return 
    return ans if ans != 2505 else -1


print(solve())