[백준] 18405. 경쟁적 전염 - Python (BFS 사용 X)

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

18405번: 경쟁적 전염

---

• 접근법 
  • (X,Y)에 바이러스 i가 전염되었다 == 바이러스 i가 (X,Y)에 가장 먼저 도착하였다.
  • 그러므로, S초 후 (X,Y)에 존재하는 바이러스 == S초 이내에 가장 먼저 도착한 바이러스 i
  • 바이러스 i와 (X,Y)와의 거리를 각각 구한 후 거리가 S 이내이면서
    • 거리가 가장 가깝고 바이러스 번호가 가장 작은 것이 답
• 코드

import sys
input = sys.stdin.readline

# 시험관의 크기, 바이러스 종류
N,K = map(int,input().split())
# 시험관
arr = [list(map(int,input().split())) for _ in range(N)]

# S초 후 (X,Y)에 존재하는 바이러스 종류 찾기
S,X,Y = map(int,input().split())

# 바이러스와 (X,Y)의 거리 최소
virus_d = [float('inf') for _ in range(K+1)]

# 바이러스와의 거리 체크
for r in range(N):
    for c in range(N):
        if arr[r][c] != 0:
            virus_d[arr[r][c]] = min(virus_d[arr[r][c]],abs(r-(X-1))+abs(c-(Y-1)))

answer = sorted([[i,v] for i,v in enumerate(virus_d)],key=lambda x:(x[1],x[0]))

# S초 안에 도착할 수 있는 바이러스 번호
answer = []
for idx, d in enumerate(virus_d):
    # S초 안에 전염될 수 있는가?
    if d <= S:
        answer.append([idx,d])

# S초 안에 전염될 수 있으면서 바이러스 번호가 가장 낮은 것이 답
answer.sort(key=lambda x:(x[1],x[0]))

# 어떤 바이러스도 S초 이내에 도달할 수 없다면 0
if not answer:
    print(0)
else:
    print(answer[0][0])