[백준_18405] 경쟁적전염 python

와 이문제 생각보다 매우 까다로웠다.

bfs내에서 종료조건을 걸어줘야,

시간초과에 걸리지 않고 문제를 해결할 수 있다.

# n, k 입력
n, k = map(int, input().split())

# lab
lab = [
    list(map(int, input().split()))
    for _ in range(n)
]

# s, r, c 입력
s, r, c = map(int, input().split())

# 함수들
# in_range(x, y)
def in_range(x, y):
    return 0 <= x < n and 0 <= y < n

# can_go(x, y)
def can_go(x, y):
    # 범위 내에 있고, 방문한 적 없고, 빈칸이면 가능
    return in_range(x, y) and not lab[x][y]

# bfs()
def bfs():
    # cnt
    cnt = 0
    while q:
        # 종료조건
        if cnt == s:
            break
        
        dxs, dys = [-1, 1, 0, 0], [0, 0, -1, 1]
        for _ in range(len(q)):
            virus_num, x, y = q.popleft()
            for dx, dy in zip(dxs, dys):
                nx, ny = x + dx, y + dy
                # 전염시킬 수 있으면,
                if can_go(nx, ny):
                    # 큐에 넣어주고
                    q.append((virus_num, nx, ny))
                    # 전염시켜주고
                    lab[nx][ny] = lab[x][y]
        
        # cnt 올려주기
        cnt += 1

# 설계
# 큐 사용 준비
from collections import deque
q = deque()

# 바이러스의 위치와 번호를 저장해 줄 리스트
virus_data = []

# 바이러스의 위치와 번호를 저장
for i in range(n):
    for j in range(n):
        if lab[i][j]:
            virus_data.append((lab[i][j], i, j))

# 리스트 정렬
virus_data.sort()

# 리스트에 있는 바이러스를
for virus_num, x, y in virus_data:
    # 큐에 넣어주고
    q.append((virus_num, x, y))

# bfs()
bfs()

# 출력
print(lab[r-1][c-1])