[Python/BOJ] 15812. 침략자 진아

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

15812번: 침략자 진아

문제

진아는 행성의 침략자이다. 진아의 행성 침략 방법은 너무 끔찍하기로 소문이 나 있다.

진아는 2개의 독주머니를 가지고 있는데, 독주머니는 빠른 속도로 독을 퍼트려 행성에 있는 생물을 중독시킨다고 한다. 독주머니의 독은 1초마다 인접한 지역으로 퍼질 정도로 빠르다! 진아는 바쁘기 때문에 아주 빠르게 행성을 침략하고자 한다.

당신은 진아의 조수이다. 진아는 포악하기 때문에 독주머니를 설치할 최적의 위치를 알려주지 않는다면 고문을 당할 수도 있다! 진아에게 최적의 위치에 설치한다면 몇 초 만에 모든 마을에 독이 퍼질 수 있을지 알려주자.

먼저 2차원 지도에 마을들의 위치가 주어진다. 예를 들어 행성의 지도가 다음과 같이 주어졌을 때,

5 6
110011
000000
000000
011010
000000

맨 위의 가장 왼쪽이 0,0 이라고 할 때 (2,1) 과 (2,4) 에 독주머니를 설치한다면 3초 만에 모든 마을이 중독된다. (2, 1)은  3번째 줄의 2번째 칸이다. (행성 전체가 중독되는데 걸리는 시간을 구하는 것이 아니라 모든 마을이 중독되는데 걸리는 시간을 묻는 것이다.) 

단, 독주머니를 마을에는 둘 수 없다. 빈 공간에만 둘 수 있다. 마을에 독주머니를 뒀다간 들킬 수도 있기 때문이다.

또한, A라는 마을과 B라는 마을이 인접해있고 A라는 마을이 중독되었다면 1초 후에 B라는 마을로 전염된다. (이 문제에서 인접이란 상하좌우를 뜻한다.)

입력

2차원 공간의 세로의 크기와 가로의 크기를 의미하는 두 정수 N, M(2 ≤ N, M ≤ 20)이 주어진다.

예제 입력과 같이 마을의 지도가 주어진다. 0은 빈 공간을, 1은 마을이 있는 공간을 의미한다.

출력

가장 최적의 위치 두 곳에 독주머니를 설치 시, 몇 초 만에 행성을 초토화 시킬 수 있는지 출력하시오.

단, 독주머니를 설치하지 못하는 경우는 없다.

풀이

Code

import sys
from collections import defaultdict, deque
input = sys.stdin.readline

# 1. bfs 함수 정의
def bfs(x, y) :
    # 1-1. 현재 위치 방문 처리
    visited = [[False] * m for _ in range(n)]
    visited[x][y] = True
    # 1-2. 큐를 생성해 (현재 위치, 거리) 삽입
    queue = deque()
    queue.append((x, y, 0))
    # 1-3.
    while queue :
        # 1-3-1. 위치, 거리 인덱스 반환
        x, y, d = queue.popleft()
        # 1-3-2.
        for dir_x, dir_y in [(-1, 0), (1, 0), (0, -1), (0, 1)] :
            # 다음 위치 설정
            nx, ny = x + dir_x, y + dir_y
            # 예외처리
            if nx < 0 or nx >= n or ny < 0 or ny >= m : continue
            # 다음 위치에 방문하지 않은 경우
            if not visited[nx][ny] :
                # 해당 위치가 마을인 경우
                if graph[nx][ny] :
                    # 시간 정보 입력
                    time[info[nx, ny]] = d + 1
                # 방문 처리
                visited[nx][ny] = True
                # 큐에 (다음 위치, 거리 + 1) 삽입
                queue.append((nx, ny, d + 1))

n, m = map(int, input().split())
graph = [list(map(int, input().rstrip())) for _ in range(n)]
# 2. 마을 정보를 딕셔너리의 키로 생성
idx = 0
info = defaultdict(list)
for i in range(n) :
    for j in range(m) :
        if graph[i][j] :
            info[i, j] = idx
            idx += 1
# 3. 마을 중독 시간 리스트 생성
times = []
# 4.
for i in range(n) :
    for j in range(m) :
        # bfs 실행
        if not graph[i][j] :
            # 해당 인덱스에서의 중독 시간 리스트 생성
            time = [0] * idx
            bfs(i, j)
            # 마을 중독 시간 리스트에 현재 인덱스에서의 중독 시간 리스트 삽입
            times.append(time)
answer = float('inf')
# 5. 최소 중독 시간 비교
for i in range(len(times)) :
    for j in range(i+1, len(times)) :
        if i != j :
            # 5-1. 두 위치에서의 중독 시간 체크
            total_time = max([min(times[i][k], times[j][k]) for k in range(idx)])
            # 5-2. 최솟값 업데이트
            answer = min(answer, total_time)
# 6. 결과 출력
print(answer)