백준 18405 - 파이썬

구기성·2023년 1월 10일
0

알고리즘

목록 보기
14/31



경쟁적 전염

이 문제는 BFS를 이용해서 풀 수 있다. 입력으로는 N, K가 주어진다. N은 시험관의 크기, K는 바이러스의 종류이다. 그리고 바이러스는 낮은 번호의 바이러스부터 먼저 증식한다. 그리고 바이러스의 정보를 입력한다. S, X, Y도 입력으로 주어진다. S는 초, X, Y는 좌표이다.

나는 큐에 바이러스의 정보, 초, X좌표, Y좌표를 담아서 넣었다.
그런 다음 네방향 로직을 통해서 문제를 해결했다.
내 코드는 아래와 같다.

import sys
from collections import deque

# 인덱스 체크 함수
def checkBorder(x, y):
    if x < 0 or x >= N or y < 0 or y >= N:
        return False
    return True


N, K = map(int, sys.stdin.readline().split())
array = []
for i in range(N):
    array.append(list(map(int, sys.stdin.readline().split())))

data = []
# 바이러스의 정보 담음
for i in range(N):
    for j in range(N):
        if array[i][j] != 0:
            data.append((array[i][j], 0, i, j))  # 바이러스 정보, 초, 행 위치, 열 위치

data.sort()  # 낮은 번호의 바이러스부터 전염을 시작하기 때문
queue = deque(data)  # 큐에 삽입

S, X, Y = map(int, sys.stdin.readline().split())
dx = [0, 0, -1, 1]
dy = [-1, 1, 0, 0]

while queue:
    virus, s, x, y = queue.popleft()  # 큐에서 데이터 추출

    if s == S:  # 바이러스의 초와 종료 시간과 같으면 탈출
        break

    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]

        if checkBorder(nx, ny):  # 인덱스가 넘어버리지 않는다면
            if array[nx][ny] == 0:
                array[nx][ny] = virus  # 바이러스 전염
                queue.append((virus, s + 1, nx, ny))  # 큐에 새로운 데이터 삽입

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

0개의 댓글