[Python](BFS) 백준 18405번 : 경쟁적 전염

---

<접근 방법>

1. 우선 초기 시험관에 있는 바이러스들의 정보를 virus라는 리스트에 담은 후 종류 번호가 큰 것부터 작은 순으로 정렬시킨다.
2. S초 동안 바이러스의 전염을 시킨다.
   정렬된 virus에서 pop을 해 꺼내보면 종류 번호가 작은 것부터 꺼내지므로 꺼내서 전염시키고 새로 퍼진 바이러스는 new_virus라는 리스트에 담는다.
   1초간 전염이 끝나면 new_virus에 있는 바이러스들을 위의 1번처럼 정렬시키고 virus로 전환시킨다.

N, K = map(int, input().split())
board = [list(map(int, input().split())) for _ in range(N)]
S, X, Y = map(int, input().split())

virus = []  # 초기 시험관 속에 있는 바이러스들을 담을 리스트
for i in range(N):
    for j in range(N):
        if board[i][j]:
            virus.append((i, j, board[i][j]))
virus.sort(key=lambda x: -x[-1])    # 종류 번호가 큰-작은 순으로 정렬

for _ in range(S):  # S초 동안 시행
    new_virus = []  # 새로운 바이러스를 담을 임시 리스트
    for _ in range(len(virus)):
        ci, cj, num = virus.pop()   # 작은 번호의 바이러스부터 꺼내기
        for di, dj in ((-1, 0), (0, 1), (1, 0), (0, -1)):
            ni = ci + di
            nj = cj + dj
            if 0<=ni<N and 0<=nj<N and not board[ni][nj]:   # 범위내, 빈칸이면 전염
                new_virus.append((ni, nj, num))
                board[ni][nj] = num
    new_virus.sort(key=lambda x: -x[-1])    # 종류 번호가 큰-작은 순으로 정렬
    virus = new_virus   # new_virus를 virus로 치환 후 반복문 반복

print(board[X-1][Y-1])

예제 2의 결과

이해가 되지 않는 부분이 있으면 질문 주세요. 감사합니다.