[BOJ] #18405 경쟁적 전염 (Python)

🌱 문제

18405번: 경쟁적 전염

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

 

🌱 풀이

0. 입력 받기

n, k = map(int, input().split())
graph = []
for i in range(n):
    graph.append(list(map(int, input().split())))
s, x, y = map(int, input().split())

• 첫째줄에 시험관의 크기(n)와 바이러스의 종류의 개수(k)를 입력받습니다.
• 다음 n개에 줄에 시험관의 정보를 입력받습니다.
• 마지막 줄에 시간(s), 출력할 시험관 칸의 정보(x, y)를 입력 받습니다.

 

1. 상하좌우 방향 설정

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

바이러스는 상하좌우로 증식하므로 상, 하, 좌, 우 방향을 설정해줍니다.

 

2. 맵을 완전탐색하며 바이러스 위치 정보 저장하기

queue = deque([])
for i in range(n):
    for j in range(n):
        if graph[i][j] != 0:
            queue.append((i, j))

맨 처음 queue에는 입력받은 시험관 정보에서 바이러스가 있는 위치를 저장해줍니다.

 

3. 매 초마다 바이러스 확산시키기

for sec in range(s):

    # 매 초에 확산된 바이러스 위치 저장할 리스트
    spread = []
    while queue:
        i, j = queue.popleft()

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

            if nx < 0 or ny < 0 or nx > n - 1 or ny > n - 1:
                continue

            if graph[nx][ny] == 0 or (graph[nx][ny] > graph[i][j] and (nx, ny) in spread):
                spread.append((nx, ny))
                graph[nx][ny] = graph[i][j]

    for l in spread:
        queue.append(l)

• 이 문제는 가능 곳까지 한 번에 탐색하는 것이 아니라 매 초마다 바이러스가 상하좌우로만 확산될 수 있기 때문에 가능한 곳까지 한번에 탐색하지 않고 주어진 초(s)만큼 반복하며 반복할 때마다 queue를 업데이트합니다.
• spread 리스트는 매 초에 확산된 바이러스의 위치만 저장하는 리스트입니다. queue에 있는 바이러스를 빼내가며 상하좌우 탐색후, spread에 넣고, queue에 있는 바이러스를 모두 꺼내었을 때, queue에 spread에 저장해놓은 위치를 넣어줍니다.
• 바이러스가 확산되는 경우(spread에 넣어지는 경우)는 다음 2가지가 있습니다.
  • 확산될 위치에 아무것도 없는 경우(graph[nx][ny]가 0인 경우)
  • 확산될 위치에 현재 탐색중인 바이러스(graph[i][j])보다 현재 시간에 확산된(spread에 있는) 더 큰 바이러스가 있는 경우 (graph[nx][ny] > graph[i][j] and (nx, ny) in spread인 경우)
    (매 초마다 번호가 낮은 종류의 바이러스부터 먼저 증식하기 때문)

 

4. 출력하기

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

 

🌱 코드

# !/usr/bin/env python
# -*- coding: utf-8 -*-
# boj 18405 경쟁적 전염

import sys
from collections import deque

input = sys.stdin.readline

n, k = map(int, input().split())
graph = []
for i in range(n):
    graph.append(list(map(int, input().split())))
s, x, y = map(int, input().split())

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

queue = deque([])
for i in range(n):
    for j in range(n):
        if graph[i][j] != 0:
            queue.append((i, j))

for sec in range(s):

    # 매 초에 확산된 바이러스 위치 저장할 리스트
    spread = []
    while queue:
        i, j = queue.popleft()

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

            if nx < 0 or ny < 0 or nx > n - 1 or ny > n - 1:
                continue

            if graph[nx][ny] == 0 or (graph[nx][ny] > graph[i][j] and (nx, ny) in spread):
                spread.append((nx, ny))
                graph[nx][ny] = graph[i][j]

    for l in spread:
        queue.append(l)

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