[Seop's의 코드풀이] 백준 18405번 경쟁적 전염 - Python

이번에 풀어볼 문제는 백준 18405번 경쟁적 전염이라는 문제이다.

문제는 다음과 같다.

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

18405번: 경쟁적 전염

 

 

문제를 요약하면 다음과 같다.

N*N의 칸이 주어지며 각 칸에는 K 이하의 자연수와 0으로 구성되어 있다.
1초가 지날때마다 낮은 자연수부터 상하 좌우의 0이 해당번호로 바뀐다.(0 이외의 번호가 있을 경우는 무시)
S초 뒤에 X,Y 에 해당하는 숫자를 출력하면 된다.

 

필자가 본 문제에서 중점적으로 본 것은

바이러스의 위치를 저장하고 이에 해당하는 것에만 연산을 진행하는 방식이었다.

즉 1초가 지날때 바이러스가 있는 부분만 연산을 진행하면 된다.

순서는 딕셔너리를 이용해 정렬하였다.

 

자세한 구현방법과 전체 코드는 다음과 같다.

import sys
input = sys.stdin.readline


def spread(v_dic) :
    #  바이러스를 낮은 번호 순대로 정렬한다.
    sort_v = sorted(v_dic.items(), key= lambda x: x[0])
    new_v = dict()
    #  상하 좌우 4방향
    dx = [0, 0 ,-1, 1]
    dy = [-1, 1, 0, 0]

    for location in sort_v :
        key = location[0]
        for tx, ty in location[1] :
            for i in range(4) :
                x = tx + dx[i]
                y = ty + dy[i]
                if x >=0 and x < N and y >= 0 and y < N :
                    #  해당 칸이 0일때만 바이러스가 채워진다. 마찬가지로 dict에 저장
                    if board[y][x] == 0 :
                        board[y][x] = key
                        if key in new_v :
                            new_v[key].append([x, y])
                        else :
                            new_v[key] = [ [x, y ] ]
    return new_v

N, K = map(int, input().split(" "))
board = []
virus = dict()
for i in range(N) :
    buf = list(map(int, input().split(" ")))
    board.append(buf)
    for j in range(N) :
        #  바이러스가 존재하는 경우 dict에 키는 바이러스 번호, Value는 위치를 저장
        if buf[j] != 0 :
            if buf[j] in virus :
                virus[buf[j]].append([j, i])
            else :
                virus[buf[j]] = [[j, i]]

S , X , Y = map(int, input().split(" "))

for _ in range(S) :
    virus = spread(virus)

X -= 1
Y -= 1
if board[X][Y] == 0 :
    print(0)
else :
    print(board[X][Y])