👩‍🎓공부 - 2023.12.25 오늘의 백준 문제풀이

18405번 - 경쟁적 전염

행렬이 주어졌을 때 1초뒤 1~3까지의 바이러스가 상하좌우 한 칸씩 자기 자신으로 감염을 시킵니다.
N초가 지났을 때, 행렬의 X,Y좌표에 어떤 바이라스가 있는지 구하면 되는 문제입니다.

N,K = map(int,input().split())
graph = []
que = deque()
for _ in range(N):
    graph.append(list(map(int,input().split())))
S,X,Y = map(int,input().split())

행렬크기와 바이러스의 종류, 그래프와 시간 및 최종좌표를 입력받겠습니다.

for k in range(1,K+1):
    for i in range(N):
        for j in range(N):
            if graph[i][j] == k:
                que.append([i,j])

1~K까지의 바이러스를 차례대로 BFS안에 넣어서 전염을 시켜보도록 하겠습니다.

dx = [-1,1,0,0]
dy = [0,0,1,-1]
def bfs():
    for _ in range(S):
        for _ in range(len(que)):

이 부분이 핵심입니다. BFS의 평소 while que와는 다르게 1초,2초,3초... 일때 que의 길이만큼 (해당 초의 검사해야하는 시험관 수) 반복하여

            x,y = que.popleft()
            for i in range(4):
                nx = dx[i] + x
                ny = dy[i] + y
                
                if nx<0 or ny<0 or nx>=N or ny>=N:
                    continue 

4방향 검사를 실시해주고

                if graph[nx][ny] == 0:
                    que.append([nx,ny])
                    graph[nx][ny] = graph[x][y]

만약 바이러스가 감염 안된 구간이 있다면 전 시험관에 적힌 바이러스로 감염을 시켜주고 해당 구간도 검사 예정에 포함시키도록 합시다.

순서를 보면
1초-> 1,2,3....바이러스가 적힌 상하좌우 한칸만 감염 실행 (다음 후보 que에 append)
2초-> 1,2,3....바이러스가 적힌 다음 후보들 상하좌우 한칸만 감염 실행 (그다음 후보 que에 append)
2초-> 1,2,3....바이러스가 적힌 그다음 후보들 상하좌우 한칸만 감염 실행 (그다다음 후보 que에 append)
,
.
.
이런씩으로 이루어진다고 볼 수 있습니다.

bfs()
print(graph[X-1][Y-1])

마지막으로 함수를 실행하고 출력하면 답이 정상적으로 나오는 걸 확인할 수 있습니다.