[BOJ] 18405 - 경쟁적 전염

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

18405번: 경쟁적 전염

import sys
from collections import deque
n, k = map(int, input().split())
graph = [list(map(int, sys.stdin.readline().rstrip().split())) for i in range(n)]
s, x_result, y_result = map(int, input().split())

dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]

cnt = 0
virus = []
for i in range(n):
    for j in range(n):
        if graph[i][j] != 0:
            virus.append((i, j, graph[i][j], cnt))
            
virus.sort(key = lambda x: x[2])

queue = deque(virus)

while queue:
    x, y, num, cnt = queue.popleft()
    
    if cnt == s:
        break
    
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        
        if nx < 0 or nx >= n or ny < 0 or ny >= n:
            continue
        
        if graph[nx][ny] == 0:
            graph[nx][ny] = num
            queue.append((nx, ny, num, cnt + 1))
            
print(graph[x_result - 1][y_result - 1])

 

이 문제는 BFS를 이용하여 풀 수 있는 문제이다. 

for i in range(n):
    for j in range(n):
        if graph[i][j] != 0:
            virus.append((i, j, graph[i][j], cnt))
            
virus.sort(key = lambda x: x[2])

그래프를 입력받을 때, 0이 아닌 바이러스가 있는 부분들에 대한 좌표를 따로 virus라는 리스트를 만들어서 그 좌표값들에 대해서만 BFS를 수행하면 된다. 다만 낮은 번호의 바이러스부터 증식한다는 점에서 바이러스 번호를 기준으로 오름차순 정렬을 수행하여 낮은 번호의 바이러스부터 큐에 들어가도록 해주어야 한다.

 

if graph[nx][ny] == 0:
            graph[nx][ny] = num
            queue.append((nx, ny, num, cnt + 1))

바이러스를 전염시킬 때는 전염시킬 노드를 큐에 넣어주는데 이때 cnt ++을 해줌으로써 몇 초 후에 전염된 노드인지 판별할 수 있다.

---

느낀 점 / 의문

바이러스가 있는 노드만 따로 리스트를 만들어서 작은 숫자의 바이러스부터 정렬하는 테크닉이 핵심이었던 것 같다.

또한 튜플 형태로 좌표와 숫자, cnt를 한 번에 관리하는 방법도 자주 쓰게 될 것 같다.

 

아이디어 떠올리는 것이나 구현은 그렇게까지 오래 걸리지 않았는데 테스팅까지 다 하고 처음 제출한 코드가 백준 사이트에서 계속 틀렸다고 나와서 미칠 뻔했다. 다른 코드를 찾아 비교해봐도 문제 될 점이 없었다. 근데 허무한 점이 단지 print문의 위치만 바꿨는데 정답 판정을 받았다. 아직도 의문이다... 내가 잘못 알고 있는 무언가가 있나???

 

틀린 코드??? (print문의 위치만 다름)

import sys
from collections import deque
n, k = map(int, input().split())
graph = [list(map(int, sys.stdin.readline().rstrip().split())) for i in range(n)]
s, x_result, y_result = map(int, input().split())

dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]

cnt = 0
virus = []
for i in range(n):
    for j in range(n):
        if graph[i][j] != 0:
            virus.append((i, j, graph[i][j], cnt))
            
virus.sort(key = lambda x: x[2])

queue = deque(virus)

while queue:
    x, y, num, cnt = queue.popleft()
    
    if cnt == s:
    	print(graph[x_result - 1][y_result - 1]) # 이 부분에 넣으면 왜 안되지?
        break
    
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        
        if nx < 0 or nx >= n or ny < 0 or ny >= n:
            continue
        
        if graph[nx][ny] == 0:
            graph[nx][ny] = num
            queue.append((nx, ny, num, cnt + 1))