문제

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

문제 설명

바이러스가 상하좌우로 퍼져나가야 하는데 이건 BFS의 로직 완전 그 자체이다. 너무나도 전형적인 BFS 문제.. 다만 주의해야할 점이 번호가 낮은 바이러스가 우선적으로 퍼져나가야 한다는 점이다!

풀이

번호가 낮은 바이러스부터 퍼져나가게 하려면 BFS에서 사용하는 자료구조인 큐의 특성을 이용하면 된다. 큐는 FIFO(First In, First Out)의 자료구조이므로 큐에 바이러스 번호가 낮은 순서대로 넣어주면 된다. 그럼 큐에서 번호가 낮은 순서대로 꺼내어 처리하고 다시 그 순서대로 큐에 넣어주어 번호의 순서를 유지한채 매초 바이러스가 퍼지는 과정을 구현할 수 있다.

q = deque()
for i in range(1, K + 1):
    for y in range(N):
        for x in range(N):
            if board[y][x] == i:
                q.append((x, y, 0))

위와 같이 deque를 통해 큐를 하나 선언해주고, 바이러스 번호가 낮은 순서대로 시험관 전체를 순회하며 큐에 바이러스의 위치와 시간초를 넣어준다.

d = [(1, 0), (-1, 0), (0, 1), (0, -1)]
while q:
    x, y, sec = q.popleft()
    if sec == S:
        break
    for dx, dy in d:
        nx, ny = x + dx, y + dy
        if 0 <= nx < N and 0 <= ny < N and board[ny][nx] == 0:
            board[ny][nx] = board[y][x]
            q.append((nx, ny, sec + 1))

이후 동서남북으로 범위를 초과하지 않으면서 아직 전염되지 않은 지역, 즉 값이 0인 지역을 현재 바이러스 번호(board[y][x])로 바꿔준다. 그리고 시간초를 1씩 늘려주는데 시간초가 S와 같아지는 순간 탐색을 종료하면 된다.

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

이후 (X, Y)를 출력하면 되는데 (1, 1) 부터라고 명시되어 있으니 1씩 빼주어 그 위치에 값을 출력해주면 통과!

최적화

통과는 했지만 소요 시간이 너무 길었다... 아무래도 K가 최대 1000이고 N은 200이어서 다음 3중 for문의 시간복잡도가 너무 높은 것 같았다. 최대 $1000 \times 200 \times 200$이 되므로 느린게 당연했다.

q = deque()
for i in range(1, K + 1):
    for y in range(N):
        for x in range(N):
            if board[y][x] == i:
                q.append((x, y, 0))

그래서 애초에 번호가 낮은 순서대로 넣어줄 필요없이 그냥 일단 다 넣은 다음에 번호 순서대로 정렬을 해주면 된다! 다음과 같이 말이다.

board = [list(map(int, input().split())) for _ in range(N)]
S, X, Y = map(int, input().split())

q = []
for y in range(N):
    for x in range(N):
        if board[y][x] > 0:
            q.append((board[y][x], x, y, 0))
q = deque(sorted(q, key=lambda x: x[0]))

그냥 정렬을 하면 x, y, sec 모두 정렬 조건으로 삼게 되므로 바이러스 번호인 0번 인덱스 값만 정렬 조건으로 삼는게 좋다. 그 결과 다음과 같이 소요 시간을 대폭 줄일 수 있었다!

큰 차이는 나지 않겠지만 $N \times N$으로 두 번 순회할 필요없이 map 정보 입력 당시에 큐 역시 초기화 해주는게 좋을 것이다.

board = []
q = []
for y in range(N):
    board.append(list(map(int, input().split())))
    for x in range(N):
        if board[y][x] > 0:
            q.append((board[y][x], x, y, 0))
S, X, Y = map(int, input().split())

q = deque(sorted(q, key=lambda x: x[0]))

4ms 줄였다..ㅋㅋ

전체 코드

import sys
from collections import deque

input = sys.stdin.readline

N, K = map(int, input().split())
board = []
q = []
for y in range(N):
    board.append(list(map(int, input().split())))
    for x in range(N):
        if board[y][x] > 0:
            q.append((board[y][x], x, y, 0))
S, X, Y = map(int, input().split())

q = deque(sorted(q, key=lambda x: x[0]))
d = [(1, 0), (-1, 0), (0, 1), (0, -1)]
while q:
    i, x, y, sec = q.popleft()
    if sec == S:
        break
    for dx, dy in d:
        nx, ny = x + dx, y + dy
        if 0 <= nx < N and 0 <= ny < N and board[ny][nx] == 0:
            board[ny][nx] = i
            q.append((i, nx, ny, sec + 1))

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

후기

코드 자체는 기본적인 BFS 이므로 어렵지 않은 문제였지만 번호가 낮은 바이러스부터 퍼져나가야하는 조건과 큐의 특징인 FIFO와의 연관성을 떠올리지 못하면 조금 난감할 수 있는 문제인 것 같아 글을 작성하게 되었다. 자료구조의 특성을 잘 이해해야 함을 느낀 문제였다!