백준[ 18405 | Python ] 경쟁적 전염

문제

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

풀이

문제에서 고려해야할 점은 아래와 같다.

• 1초마다 상,하,좌,우 방향으로 증식한다.
• 번호가 낮은 종류의 바이러스부터 먼저 증식한다.

이를 고려하며 움직일 4방향에 관한 인덱스를 만들어주고, 시험관이 맞닿아 있는 곳과 가장 가깝고 숫자가 낮은 바이러스가 증식될 것이기 때문에 넓이 우선 탐색 방식인 BFS를 활용한다.
번호가 낮은 바이러스를 먼저 증식시키기 위해서는 먼저 추출해낸 바이러스들의 종번호를 토대로 정렬해준다.
이를 토대로 BFS를 시행한다.

import sys
from collections import deque

input = sys.stdin.readline
n, k = map(int, input().split())
board = [list(map(int,input().split())) for _ in range(n)]

sxy = list(map(int, input().split()))
S,X,Y = sxy[0],sxy[1],sxy[2]
dirs = [[0,1],[0,-1],[1,0],[-1,0]]
virus = []
for i in range(n):
    for j in range(n):
        if board[i][j] != 0 :#바이러스들의 인덱스가 필요
            virus.append((board[i][j],i,j))
virus.sort(key = lambda x:(x[0]))#종 번호가 작은 순서대로 증식

def infection(vx, vy, s):
    q = deque(virus)
    sec = 0
    while q:
        if s == sec:
            break
        for _ in range(len(q)):
            _, qx, qy = q.popleft()
            for d in range(4):
                dx, dy = map(int, dirs[d])
                x = qx+dx
                y = qy+dy
                if 0<=x<n and 0<=y<n and board[x][y] == 0:
                    board[x][y] = board[qx][qy]
                    q.append((board[i][j],x, y))#증식 시키고 가장자리 그 종의 인덱스를
        sec+=1                                  #새로 큐에 넣어줌
    return board[X-1][Y-1]

print(infection(X,Y,S))  

생각 & 정리

한동안 DP문제에 집중하다가 구현 또한 많이 중요하겠다라는 생각에 접했는데,
역시나 구현문제들에서는 여러 기법이 같이 나와 전체적으로 공부할 수 있겠다는 생각이 들었다.
특히 그래프 관련 문제들을 이전에 해결할 때 깊게는 보지 않았던 탓에 쉽지 않았고 다시 공부해야되겠다는 생각이 들었다.