경쟁적 전염(백준 18405번)

경쟁적 전염

18405번: 경쟁적 전염

18405번: 경쟁적 전염

이 문제의 경우 bfs 알고리즘을 사용하면 해결할 수 있다.

 

각 종류의 바이러스들이 있는 2차원 배열이 있다. 바이러스는 1초가 지나면 인접한 정점으로 옮겨간다. 이 때 인정한 정점에 두 종류 이상의 바이러스가 전파될 수 있는데, 이 때는 해당 정점의 값이 작은 바이러스가 먼저 전파된다고 한다.

 

경과가 지나서 다른 정점에 전파되는 유형의 문제는 for 루프를 돌면서 정점 하나 하나 돌면서 먼저 큐에 해당 정점의 정보를 넣어줘야한다.

 

그렇지 않으면 먼저 bfs한 정점으로 인해 다음 정점의 bfs에 문제가 생길수 있다.

 

그리고 경과가 지나는 문제의 경우 큐에 시간이 지남을 저장하는 정보를 같이 넣어줘서 인접 정점들로 탐색이 번져나갈 때 탐색이 시작된 지점과 차이를 둬야한다.

while q:
        # t에 시간이 지남을 저장한다.
	vir, cx, cy, t = q.popleft()
	if t == s:
	    break
	for dir in range(4):
	    nx = dx[dir] + cx
	    ny = dy[dir] + cy
	    if 0 <= nx < n and 0 <= ny < n:
	        if not visited[nx][ny]:
	            if graph[nx][ny] == 0:
	                graph[nx][ny] = vir
                        # 현재 정점에서 전파된 정점이므로 몇초가 지났음을 저장해둬야한다.
                        # 1초가 지났음을 t+1로 표현한다.
	                q.append((graph[nx][ny], nx, ny, t+1))
	                visited[nx][ny] = True

 

그리고 인정한 정점에 두 종류 이상의 바이러스가 전파될 수 있음으로 작은 값이 우선적으로 탐색될 수 있도록 큐에 넣기전에 바이러스값을 기준으로 정렬을 해준다.

for i in range(n):
    for j in range(n):
        if graph[i][j] > 0:
            q.append((graph[i][j], i, j, 0))
            visited[i][j] = True
q.sort()
bfs(q)

 

전체코드

# 경쟁적 전염

import sys
from collections import deque

n, k = map(int, sys.stdin.readline().split())
graph = []
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]
visited = [[False for _ in range(n)] for _ in range(n)]

q = []
for _ in range(n):
    graph.append(list(map(int, sys.stdin.readline().split())))
s, x, y = map(int, sys.stdin.readline().split())

def bfs(queue):
    if s == 0:
        return graph[x-1][y-1]

    q = deque(queue)

    while q:
        vir, cx, cy, t = q.popleft()

        if t == s:
            break
        
        for dir in range(4):
            nx = dx[dir] + cx
            ny = dy[dir] + cy
            if 0 <= nx < n and 0 <= ny < n:
                if not visited[nx][ny]:
                    if graph[nx][ny] == 0:
                        graph[nx][ny] = vir
                        q.append((graph[nx][ny], nx, ny, t+1))
                        visited[nx][ny] = True

        
for i in range(n):
    for j in range(n):
        if graph[i][j] > 0:
            q.append((graph[i][j], i, j, 0))
            visited[i][j] = True
q.sort()
bfs(q)
print(graph[x-1][y-1])

---

이와 비슷한 문제로 토마토, 탈출 등이 있다.

토마토

7569번: 토마토

7569번: 토마토

탈출

3055번: 탈출

3055번: 탈출

 

바이러스는 1초가 지나면 인접한 정점으로 옮겨간다.

그리고 토마토나 탈출의 경우도 하루가 지나면 토마토가 익거나, 홍수가 차오르는, 로직을 바이러스에서 사용했던것처럼 시간이 경과함을 저장하는 t 변수를 사용해서 표현 할 수 있다.