• 문제: https://www.acmicpc.net/problem/18405

설명

이전에 풀었던 토마토와 빙산과 비슷한 느낌을 받았다.
다만 본인은 문제에 나온 날짜만큼 반복문을 돌려, 총 3중 for문을 마주했는데 그렇게 풀지 않아도 된다.

✔️ 본인 문제 해결 방법

1. 매초마다 for문을 돌면서 방문하지 않았고, 0이 아닌 바이러스들을 queue에 담는다.

2. queue를 비우면서, 방문할 수 있는 지점을 확인한다.

   • 아직 채워지지 않았다면 -> 출발한 시점의 값을 채워준다.
   • 이미 채워진 지점이라면 -> 채워진 지점과 이전에 출발한 지점을 비교하여 더 작은 것을 업데이트해준다.(낮은 숫자로 채우기 위해 그렇게 했다.)

이렇게 작성하면 python으로 작성했을 때, 시간초과 나고 pypy로 하면 통과한다.

import heapq
from sys import stdin as s
from collections import deque

n, k = map(int, s.readline().split())

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

virus = []

for i in range(n):
    virus.append(list(map(int, s.readline().split())))

ss, y, x = map(int, s.readline().split())

visited = [[False for _i in range(n)] for _j in range(n)]

def bfs():
    while len(queue) > 0:
        now_y, now_x = queue.popleft()
        for dir in range(4):
            new_y = now_y + dy[dir]
            new_x = now_x + dx[dir]

			if new_y < 0 or new_y >= n or new_x < 0 or new_x >= n:
                continue

			if virus[new_y][new_x] == 0:
                virus[new_y][new_x] = virus[now_y][now_x]

			# 이미 채워진 지점이라면 이전 것과 비교하여 작은 것을 업데이트해준다.
            if virus[new_y][new_x] != 0 and not visited[new_y][new_x]:
                virus[new_y][new_x] = min(virus[new_y][new_x], virus[now_y][now_x])

queue = deque()

for t in range(ss):
    for i in range(n):
        for j in range(n):
            # 방문하지 않았고,
            if not visited[i][j] and virus[i][j] != 0:
                visited[i][j] = True
                queue.append((i, j))
    bfs()

print(virus[y - 1][x - 1])

💪 개선된 풀이
사실 매초마다 방문할 곳을 저장하고, bfs를 도는 것은 비효율적이다. 또 바이러스가 먹힌 곳을 작은 값으로 업데이트하는 것보다 처음부터 작은 값부터 먹히도록 구현한다면, 값을 채울 때 비교하는 작업을 하지 않아도 된다.

코드리뷰 시간에 동료의 코드를 확인해보니,
1) queue에 추가한 바이러스의 값을 정렬하여 탐색하고,
2) queue에 있는 값이 모두 빠져나갈 때까지 반복문을 돌다가 시간이 도달하면 종료하는 방식이었다.

코드로 살펴보겠다.

from collections import deque

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

n, k = map(int, input().split())

board = []
virus = []

for i in range(n):
	row = list(map(int, input().split()))
    board.append(row)
    for j in range(n):
    	if row[j] != 0:
        	# virus 번호, 시간, 좌표
        	virus.append((row[j], 0, i, j))

# 바이러스 순서대로 정렬
virus.sort()

s, x, y = map(int, input().split())

q = deque(virus)

while q:
	v, t, now_x, now_y = q.popleft()
    if t == s:
    	break
	for i in range(4):
    	nx = now_x + dx[i]
        ny = now_y + dy[i]
        # 범위를 벗어나면 무시
        if nx < 0 or nx >= n or ny < 0 or ny >= n:
        	continue
		# 이미 바이러스가 있다면 무시
        if board[nx][ny] != 0:
        	continue
		# 새로운 바이러스 추가
        board[nx][ny] = v
        q.append((v, t+1, nx, ny))

print(board[x-1][y-1])

동료들의 풀이 덕분에 내가 고민했던 것을 더 효과적으로 해결할 수 있는 방법을 터득할 수 있었다. 빙산 문제와 토마토 문제를 풀면서 이 부분을 연습했다고 생각했는데 아직 완성되지 않은 것 같다. 이 부분은 다시 복습하는 것이 필요할 것 같다.