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

# 18405 경쟁적 전염
https://www.acmicpc.net/problem/18405

18405번: 경쟁적 전염

코드

from collections import deque

n, k = map(int, input().split())

graph = []
data = []

for i in range(n):
  graph.append(list(map(int, input().split())))
  for j in range(n):
    if graph[i][j] != 0:
      data.append((graph[i][j], 0, i, j))

data.sort()
q = deque(data)

s, x, y = map(int, input().split())

dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

while q:
  
  virus, time, i, j = q.popleft()

  if time == s:
    break

  for i in range(4):
    nx = i + dx[i]
    ny = j + dy[i]
    if (0 <= nx and nx < n and 0 <= ny and ny < n and graph[nx][ny] == 0):
      graph[nx][ny] = virus
      q.append((virus, time+1, nx, ny))

print(graph[x-1][y-1])

📝 풀이

1.

바이러스는 1초마다 상하좌우 방향으로 증식해 나가고, 어떤 특정 칸에 바이러스가 존재한다면 그 곳으로는 바이러스가 들어갈 수 없다는 조건

=> DFS가 아닌 BFS로 해결해야 된다고 느꼈다. 

 

2.

매 초마다 번호가 낮은 종류의 바이러스부터 먼저 증식한다.

=> 바이러스의 종류가 1, 2, 3일 경우에는 겹치더라도 1이 우선적으로 전염되어야 한다. BFS를 진행할 때 번호가 낮은 종류의 바이러스부터 큐에 넣고 시작해야 한다.

 

3.

시험관의 크기와 바이러스의 위치 정보가 주어졌을 때, S초가 지난 후에 (x, y)에 존재하는 바이러스의 종류를 출력하라. 없다면 0을 출력해라.

-> 바이러스가 생성될 때마다 S초를 하나씩 늘려주는 로직 필요

🔓 코드 뜯어보기

from collections import deque

# 크기 및 바이러스 종류
n, k = map(int, input().split())

# 바이러스 정보 저장
graph = []
# 바이러스의 추가 정보 저장
data = []

for i in range(n):
  graph.append(list(map(int, input().split()))) # [[1, 0, 2], [0, 0, 0], [3, 0, 0]]
  # 바이러스의 추가 정보 저장
  for j in range(n):
    # 해당 위치에 바이러스가 존재하는 경우 (0이 아니라면 바이러스)
    if graph[i][j] != 0:
      # 바이러스 정보저장 (바이러스 종류, 확산 시간, x축 위치, y축 위치)
      data.append((graph[i][j], 0, i, j))

BFS를 사용해야 하므로 from collections import deque 라이브러리를 불러와준다.

사격형 크기 N값과 바이러스 종류 K값을 받아오고 N의 크기만큼 graph를 생성해준다.

반복문으로 그래프를 돌면서 0이 아닌 값, 즉 바이러스 인 정보들을 data에 넣어준다.

바이러스 종류와, 시간, X축 위치, Y축 위치를 data에 삽입해준다.

# 바이러스를 번호가 낮은 순서대로 정렬
data.sort()
# 바이러스 추가 정보를 큐로 변환
q = deque(data)

# s초와 (x,y)에 존재하는 바이러스의 종류
s, x, y = map(int, input().split())

# 상하좌우 이동 좌표
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

바이러스가 낮은 번호부터 증식하므로, 초기 큐에 낮은 바이러스부터 삽입하기 위해 sort로 정렬시켜준다.

구해야 하는 값인 s, x, y를 저장시켜주고 상하좌우로 움직일 dx, dy를 만들어준다.

while q:
  
  # q의 첫번째 원소를 각각에 할당
  virus, time, i, j = q.popleft()

  # 현재 위치의 바이러스가 S초까지 확산된 바이러스라면 종료
  if time == s:
    break

  # 상하좌우 계산
  for i in range(4):
    nx = i + dx[i] # dx = [-1, 1, 0, 0]
    ny = j + dy[i] # dy = [0, 0, -1, 1]
    # 범위 설정
    if (0 <= nx and nx < n and 0 <= ny and ny < n and graph[nx][ny] == 0):
      # 그래프에 바이러스 확산 표시
      graph[nx][ny] = virus
      # 큐에 삽입 (시간 +1)
      q.append((virus, time+1, nx, ny))

print(graph[x-1][y-1]) # [[1, 1, 2], [1, 1, 2], [3, 3, 2]]

while문을 통해 q를 실행시켜주고, q에 담긴 바이러스값, 시간, 위치값을 popleft를 통해 할당시켜 준다.

만약에 time이 문제에서 주어진 s와 같다면 while문을 종료 시켜준다.

상하좌우 4방향을 탐색하기 위해 range(4)로 설정해주고, nx와 ny에 이동값을 넣어준다. 

만약 nx, ny가 0보다 크거나 같고 n(사각형)범위 내에 있으며 그 값이 0이라면 그래프에 바이러스 확산 표시를 해준다.

그리고 다시 q에 바이러스와 증가된 시간, 이동값을 넣어준다.

while문이 끝나게 되면 문제에서 원하는 x, y의 바이러스 종류를 출력시켜주는데, 예제의 graph 인덱스는 가로 0~2, 세로 0~2 이므로 각각 -1씩 해준다.

 

참고

https://wooono.tistory.com/557