[baekjoon] 백준 18405번(파이썬): 경제적 전염

문제

18405번: 경쟁적 전염

알고리즘

- bfs 탐색을 통해 문제를 수행한다.

- 바이러스의 번호와 x좌표, y좌표, 시간을 리스트에 넣고 오름차순으로 정렬하여 큐에 넣는다.

- 큐에 넣은 리스트를 하나씩 탐색하여 주위에 있는 바이러스가 존재하지 않는 칸에 증식한다.

- 측정 시간과 현재 시간이 같으면 종료하여 특정 위치에 존재하는 바이러스의 번호를 출력한다.

코드

import sys
from collections import deque


# bfs 탐색
def bfs():
    # 상/하/좌/우
    dx = [-1, 1, 0, 0]
    dy = [0, 0, -1, 1]

    queue = deque(temp)

    while queue:

        num, a, b, cnt = queue.popleft()

        # 현재 시간과 측정 시간이 같으면 종료
        if cnt == s:
            # return graph[x - 1][y - 1] 왜 이건 안되는지 모르겠다.
            break

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

            # 범위 내에 있고 탐색하지 않았으면 탐색
            if 0 <= nx < n and 0 <= ny < n and graph[nx][ny] == 0:
                # 번호를 현재 바이러스 번호로 초기화
                graph[nx][ny] = num
                queue.append([num, nx, ny, cnt + 1])

    # 특정 위치에 바이러스가 존재하는지 출력
    # 0, 0부터 시작 했으므로 -1을 해준 좌표 확인
    return graph[x - 1][y - 1]


n, k = map(int, sys.stdin.readline().split())
graph = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]
s, x, y = map(int, sys.stdin.readline().split())
temp = [] # 바이러스가 들어있는 좌표 확인

for i in range(n):
    for j in range(n):
        if graph[i][j] != 0:
            # 바이러스 번호, x좌표, y좌표, 시간
            temp.append([graph[i][j], i, j, 0])

# 번호가 작은 바이러스 부터 확인하기 위해 오름차순 정렬
temp.sort()

print(bfs())

github

GitHub - junjange/CodingTest: 내가 푼 코딩 테스트 문제와 해결법