[백준/파이썬/Python] 18405번 경쟁적 전염

문제

NxN 크기의 시험관이 있다. 시험관은 1x1 크기의 칸으로 나누어지며, 특정한 위치에는 바이러스가 존재할 수 있다. 모든 바이러스는 1번부터 K번까지의 바이러스 종류 중 하나에 속한다.

시험관에 존재하는 모든 바이러스는 1초마다 상, 하, 좌, 우의 방향으로 증식해 나간다. 단, 매 초마다 번호가 낮은 종류의 바이러스부터 먼저 증식한다. 또한 증식 과정에서 특정한 칸에 이미 어떠한 바이러스가 존재한다면, 그 곳에는 다른 바이러스가 들어갈 수 없다.

시험관의 크기와 바이러스의 위치 정보가 주어졌을 때, S초가 지난 후에 (X,Y)에 존재하는 바이러스의 종류를 출력하는 프로그램을 작성하시오. 만약 S초가 지난 후에 해당 위치에 바이러스가 존재하지 않는다면, 0을 출력한다. 이 때 X와 Y는 각각 행과 열의 위치를 의미하며, 시험관의 가장 왼쪽 위에 해당하는 곳은 (1,1)에 해당한다.

예를 들어 다음과 같이 3x3 크기의 시험관이 있다고 하자. 서로 다른 1번, 2번, 3번 바이러스가 각각 (1,1), (1,3), (3,1)에 위치해 있다. 이 때 2초가 지난 뒤에 (3,2)에 존재하는 바이러스의 종류를 계산해보자.

입력

첫째 줄에 자연수 N, K가 공백을 기준으로 구분되어 주어진다. (1 ≤ N ≤ 200, 1 ≤ K ≤ 1,000) 둘째 줄부터 N개의 줄에 걸쳐서 시험관의 정보가 주어진다. 각 행은 N개의 원소로 구성되며, 해당 위치에 존재하는 바이러스의 번호가 공백을 기준으로 구분되어 주어진다. 단, 해당 위치에 바이러스가 존재하지 않는 경우 0이 주어진다. 또한 모든 바이러스의 번호는 K이하의 자연수로만 주어진다. N+2번째 줄에는 S, X, Y가 공백을 기준으로 구분되어 주어진다. (0 ≤ S ≤ 10,000, 1 ≤ X, Y ≤ N)

출력

S초 뒤에 (X,Y)에 존재하는 바이러스의 종류를 출력한다. 만약 S초 뒤에 해당 위치에 바이러스가 존재하지 않는다면, 0을 출력한다.

풀이 방안

처음에는 각 초마다 전염을 시뮬레이션하는 코드를 작성하려고 했으나, 머리가 아파서 더 간단한 방법이 없을까 생각해보았다.

 

아래 그림에서 (3, 3) 자리에 전염될 바이러스는 무엇일까? 똑같이 두 칸 떨어져 있는 2와 3, 그 중에서도 더 작은 2이다.

좀 더 생각해보면, (x, y)에 존재하는 바이러스는 (x, y)에서 가장 가까운 지점의 바이러스라고 할 수 있다. 즉 0이 아닌 값을 가지는 지점 중 (x, y)로부터 가장 가까운 곳을 찾으면 된다.

 

추가로 이 문제에는 1. 값이 더 작은 바이러스가 먼저 차지한다는 것과, 2. 제한 시간이 s초라는 조건이 있다.

1. 만약 거리가 같은 지점이 있다면, 값이 더 작은 바이러스가 목적지를 차지한다.

2. 1초에 한 칸씩 전염되므로, 제한 시간이 s초라면 최단 경로가 s칸 이하여야 한다.

코드

목적지에서부터 bfs 탐색을 시작했다. 코드 설명은 주석으로 작성하였다.

# 경쟁적 전염
import sys, collections
sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline

def bfs(start_x, start_y):
    dx = [-1, 1, 0, 0]
    dy = [0, 0, -1, 1]
    # 목표 지점에서부터
    # 조건 1: 최단 경로가 가장 가까운 곳
    # 조건 2: 최단 경로가 같다면 바이러스 번호가 더 작은 곳
    queue = collections.deque()
    queue.append((start_x, start_y))
    visited[start_x][start_y] = 1
    ans = (s+2, k)
    
    while queue:
        (x, y) = queue.popleft()
        
        for i in range(len(dx)):
            nx = x + dx[i]
            ny = y + dy[i]
            
            # 유효한 범위 내에 있고, 방문하지 않았을 때
            if 0 < nx <= n and 0 < ny <= n and not visited[nx][ny]:
                visited[nx][ny] = visited[x][y] + 1  # 거리 저장
                
                if graph[nx][ny]:                              # 해당 위치에 바이러스가 있고
                    if (visited[nx][ny], graph[nx][ny]) < ans: # 거리가 작거나 거리가 같고 바이러스 수가 작으면
                        ans = (visited[nx][ny], graph[nx][ny]) # 거리와 바이러스 종류 갱신
                        
                # 바이러스가 없다면 최단 경로가 저장된 값보다 작을 때만 큐에 추가
                elif visited[nx][ny] < ans[0]: 
                    queue.append((nx, ny))
    return ans


# 입력
n, k = map(int, input().split())            # 시험관의 크기, 최대 바이러스 번호

graph = [[0] for _ in range(n+1)]           # 시험관
visited = [[0] * (n+1) for _ in range(n+1)] # 방문 체크
for i in range(1, n+1):
    graph[i] += list(map(int, input().split()))
s, x, y = map(int, input().split())         # 초, 목표 지점

if graph[x][y]:       # 이미 바이러스가 존재하는 곳이면 -> 최소 케이스 확인 중요...
    print(graph[x][y])
else:
    # 연산
    ans = bfs(x, y)

    # 출력
    if ans[0] == s+2: # 제한 시간 안에 전염되지 않았으면
        print(0)
    else:
        print(ans[1])