[백준 18405] 경쟁적 전염

www.acmicpc.net/problem/18405

18405번: 경쟁적 전염

from collections import deque

N,K = map(int,input().split())
mat = [list(map(int,input().split())) for i in range(N)]
S,X,Y = map(int,input().split())
dx=[0,0,1,-1]
dy=[1,-1,0,0]
start = [] # 바이러스 종류, x,y좌표

for i in range(N):
    for j in range(N):
        if mat[i][j] != 0:
            start.append([mat[i][j],i,j])

start.sort()

visited = [[0 for i in range(N)] for j in range(N)]
for i in start:
    kind,tx,ty = i
    visited[tx][ty] = kind
q = deque(start)

cnt=0
while q:
    q_size = len(q)
    cnt+=1
    if cnt == S+1:
        break
    for _ in range(q_size):
        kind,tx,ty = q.popleft()

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

            if nx<0 or nx == N or ny<0 or ny == N:
                continue
            if not visited[nx][ny]:
                visited[nx][ny] = kind
                q.append([kind,nx,ny])

print(visited[X-1][Y-1])

풀이

특별할게 없는 전형적인 bfs 풀이이다.

 

바이러스가 오름차순 순서대로 bfs 돌아야 하기 때문에 첫 배열에서 찾은 바이러스들을 오름차순으로 정렬해서 q에 넣어준다.

 

S번만 돌아야 하기 때문에 q_size를 측정해서 bfs 레벨을 체크해준다.

 

시간복잡도

N*N 배열이라고 할 때,

S에 따라 조금 다르겠지만 거의 모든칸을 방문하므로 O(N^2)이라 볼 수 있다.