[백준/파이썬] 18405번 경쟁적 전염

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

18405번: 경쟁적 전염

문제 해석

 

n * n 크기의 배열에 바이러스가 1~ 1000개가 존재한다.

바이러스는 상하좌우로 번지며 1번부터 차례대로 한칸씩 번진다.

빈칸이여야 바이러스가 번질 수 있다.

S초 이후에 x, y칸에 존재하는 바이러스를 출력하라 (없다면 0 출력)

 

---

코드

 

from collections import deque
input = __import__('sys').stdin.readline

# input
n, k = map(int, input().split())
arr = []
# visit = [[0] * n for _ in range(n)]
dx, dy = [-1, 1, 0, 0], [0, 0, -1, 1]
virus = [deque() for _ in range(1001)]
for i in range(n):
    arr.append(list(map(int, input().split())))
    for j in range(n):
        # 입력받을 때 맵에 0이 아닌 수가 입력되면 해당 수의 바이러스 좌표를 추가
        if arr[i][j] != 0: virus[arr[i][j]].append((i, j))
second, x, y = map(int, input().split())
target = [x - 1, y - 1]

# solve
def solve():
    def bfs():
        for _ in range(second):
            for idx in range(1, 1001):
                # idx번 바이러스가 존재하지 않을 경우 넘어가기
                if not virus[idx]: continue
                for _ in range(len(virus[idx])):
                    i, j = virus[idx].popleft()
                    for dir in range(4):
                        x, y = i + dx[dir], j + dy[dir]
                        if not(0 <= x < n and 0 <= y < n): continue
                        # 방문하지 않고 해당 칸이 비어있다면
                        if arr[x][y] == 0:
                            virus[idx].append((x, y))
                            arr[x][y] = idx
        return arr[target[0]][target[1]]
    return bfs()
        
print(solve())

---

문제 풀이

 

먼저 map을 입력받으며 0이 아닌 수 (바이러스)가 입력받는다면 큐로 이루어진 바이러스의 좌표를 담은 리스트에 넣어준다. 이때 바이러스의 idx에는 바이러스의 번호를 의미한다.

 

bfs 함수는 s초만큼 반복하며, 바이러스번호 오름차순으로 돌아간다.

단계별로 돌리기위해 바이러스 큐의 크기만큼 반복하며 바이러스가 번질 공간이 비어있다면 들어가도록 구현했다.

 

단계별 bfs, 바이러스를 담은 큐를 1000개 생성한다는 생각만 한다면 쉽게 풀 수 있는 그래프 bfs 문제이다.