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

<문제 링크>

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

18405번: 경쟁적 전염

<풀이 전략>

1. 토마토랑 비슷하게 처음에 바이러스의 좌표를 큐에 저장해두고 bfs를 돌리면된다.

2. 단 이 문제에서는 낮은 번호의 바이러스부터 전염된다는 특성이 있으므로 bfs 돌리기 직전에 큐를 한번 정렬해줘야 한다.

 

<정답 코드>

from collections import deque
import sys, os, io, atexit

input = lambda: sys.stdin.readline().rstrip('\r\n')
stdout = io.BytesIO()
sys.stdout.write = lambda s: stdout.write(s.encode("ascii"))
atexit.register(lambda: os.write(1, stdout.getvalue()))

# 220921 18405 경쟁적 감염

# 정답코드

# N: 배열의 크기, K: 바이러스 개수
N, K = map(int, input().split())
# arr: 배열
arr = [list(map(int, input().split())) for _ in range(N)]
# S: 시간, X, Y: 목표 좌표
S, X, Y = map(int, input().split())

# virus: 바이러스의 좌표를 담을 리스트
virus = []

# 바이러스의 좌표, 바이러스 종류, 탐색 시간 초깃값을 넣어준다.
for r in range(N):
    for c in range(N):
        if arr[r][c]:
            virus.append((r, c, arr[r][c], 0))

# 바이러스 종류에 따라 정렬
virus = deque(sorted(virus, key=lambda x: x[2]))

# 델타 탐색 탐색 방향
dr = [-1, 1, 0, 0]
dc = [0, 0, -1, 1]


# bfs 함수 선언
def bfs(virus=deque):

    while virus:
        r, c, virus_type, time = virus.popleft()
        # S시간만큼 탐색을 다 마쳤을 경우
        if time == S:
            # 목표 좌표의 바이러스 종류 출력
            print(arr[X - 1][Y - 1])
            return

        for i in range(4):
            nr = r + dr[i]
            nc = c + dc[i]
            # 해당 영역이 빈 공간일 때 바이러스 종류로 갱신해주면서 탐색
            if 0 <= nr < N and 0 <= nc < N:
                if arr[nr][nc] == 0:
                    arr[nr][nc] = virus_type
                    virus.append((nr, nc, virus_type, time + 1))

    print(arr[X - 1][Y - 1])
    return


# bfs 탐색 실시
bfs(virus)