백준 18405 <경쟁적 전염> Python

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

---

구현 문제같지만 사실 단순한 계산 문제입니다.

n 초가 지난 뒤 전염될 수 있는 칸은 각 행 / 열의 위치값 차이의 합이 n 인 인덱스입니다.

즉 주어진 X, Y 와 초기에 바이러스가 존재하는 칸들 중 어느 칸과 가장 가까운지 알면 무조건 해당 칸과 같은 바이러스로 감염됩니다.

다만 S 초 동안은 S 칸 만큼만 바이러스가 이동할 수 있으므로 행 / 열의 위치값 차이의 합이 S 이상일 경우 바이러스가 도달할 수 없음을 주의해야 합니다.

---

import sys

input = sys.stdin.readline


def solution(N, K, informs, S, X, Y):
    # 바이러스 위치 탐색
    v_idxs = [[] for _ in range(K+1)]
    for i in range(N):
        for j in range(N):
            if informs[i][j]:
                v_idxs[informs[i][j]].append([i, j])
    
    # X, Y 와 바이러스들 거리 계산
    # 최소 거리 / 최소 바이러스 번호
    min_dist = float('inf')
    min_v = 0
    # 낮은 번호부터 순회
    # 낮은 번호부터 해야 낮은 번호로 먼저 갱신
    for i in range(1, K+1):
        for x, y in v_idxs[i]:
            # 거리
            dist = abs(X-1-x) + abs(Y-1-y)
            # 최소거리 갱신
            if dist < min_dist:
                min_dist = dist
                # 최소 거리가 S 보다 작으면 최소 바이러스 번호 갱신
                if S >= min_dist:
                    min_v = i

    print(min_v)
    

# 입력
N, K = map(int, input().strip().split())
informs = [list(map(int, input().strip().split())) for _ in range(N)]
S, X, Y = map(int, input().strip().split())

solution(N, K, informs, S, X, Y)