[Gold V] 경쟁적 전염 - 18405

문제 링크

성능 요약

메모리: 34968 KB, 시간: 96 ms

분류

구현, 그래프 이론, 그래프 탐색, 너비 우선 탐색

문제 설명

NxN 크기의 시험관이 있다. 시험관은 1x1 크기의 칸으로 나누어지며, 특정한 위치에는 바이러스가 존재할 수 있다. 모든 바이러스는 1번부터 K번까지의 바이러스 종류 중 하나에 속한다.

시험관에 존재하는 모든 바이러스는 1초마다 상, 하, 좌, 우의 방향으로 증식해 나간다. 단, 매 초마다 번호가 낮은 종류의 바이러스부터 먼저 증식한다. 또한 증식 과정에서 특정한 칸에 이미 어떠한 바이러스가 존재한다면, 그 곳에는 다른 바이러스가 들어갈 수 없다.

시험관의 크기와 바이러스의 위치 정보가 주어졌을 때, S초가 지난 후에 (X,Y)에 존재하는 바이러스의 종류를 출력하는 프로그램을 작성하시오. 만약 S초가 지난 후에 해당 위치에 바이러스가 존재하지 않는다면, 0을 출력한다. 이 때 X와 Y는 각각 행과 열의 위치를 의미하며, 시험관의 가장 왼쪽 위에 해당하는 곳은 (1,1)에 해당한다.

예를 들어 다음과 같이 3x3 크기의 시험관이 있다고 하자. 서로 다른 1번, 2번, 3번 바이러스가 각각 (1,1), (1,3), (3,1)에 위치해 있다. 이 때 2초가 지난 뒤에 (3,2)에 존재하는 바이러스의 종류를 계산해보자.

입력

첫째 줄에 자연수 N, K가 공백을 기준으로 구분되어 주어진다. (1 ≤ N ≤ 200, 1 ≤ K ≤ 1,000) 둘째 줄부터 N개의 줄에 걸쳐서 시험관의 정보가 주어진다. 각 행은 N개의 원소로 구성되며, 해당 위치에 존재하는 바이러스의 번호가 공백을 기준으로 구분되어 주어진다. 단, 해당 위치에 바이러스가 존재하지 않는 경우 0이 주어진다. 또한 모든 바이러스의 번호는 K이하의 자연수로만 주어진다. N+2번째 줄에는 S, X, Y가 공백을 기준으로 구분되어 주어진다. (0 ≤ S ≤ 10,000, 1 ≤ X, Y ≤ N)

출력

S초 뒤에 (X,Y)에 존재하는 바이러스의 종류를 출력한다. 만약 S초 뒤에 해당 위치에 바이러스가 존재하지 않는다면, 0을 출력한다.

---

문제 풀이

문제 분석

문제는 N x N 크기의 시험관에서 바이러스가 증식하는 과정을 시뮬레이션하는 것입니다. 각 바이러스는 1초마다 상, 하, 좌, 우로 증식하며, 번호가 낮은 바이러스부터 먼저 증식합니다. S초 후 특정 좌표 (X, Y)에 존재하는 바이러스의 종류를 출력해야 합니다. 해당 위치에 바이러스가 없으면 0을 출력합니다.

접근 방법

이 문제는 BFS(너비 우선 탐색) 알고리즘을 사용하여 해결할 수 있습니다. 번호가 낮은 바이러스부터 증식해야 하므로, 바이러스를 번호 순서대로 정렬하여 큐에 넣고 BFS를 수행합니다. 각 초마다 큐에 있는 바이러스들을 기준으로 증식을 시뮬레이션하고, 다음 초에 증식할 바이러스를 새로운 큐에 저장합니다. S초 동안 이 과정을 반복한 후, 목표 좌표의 값을 확인하여 결과를 출력합니다.

구현 설명

1. 입력 및 초기화

• 입력으로 N, K, 시험관 정보, S, X, Y를 받습니다.
• 시험관 정보를 나타내는 graph 리스트를 생성합니다.
• 초기 바이러스의 위치와 종류를 queue 리스트에 튜플 형태로 저장합니다. (바이러스 종류, 행 좌표, 열 좌표)
• queue를 바이러스 종류를 기준으로 오름차순 정렬합니다.
• BFS 탐색을 위한 queue를 deque 자료구조로 변환합니다.
• 상, 하, 좌, 우 방향을 나타내는 directions 리스트를 정의합니다.

2. BFS 함수 정의

• BFS(queue) 함수는 큐에서 바이러스를 꺼내 상, 하, 좌, 우 방향으로 증식을 시도합니다.
• 새로운 큐 new_queue를 생성하여 다음 초에 증식할 바이러스를 저장합니다.
• 현재 위치가 비어있고(graph 값이 0), 범위를 벗어나지 않는 경우에만 증식을 진행합니다.
• 증식된 위치의 graph 값을 바이러스 종류로 갱신하고, new_queue에 추가합니다.
• new_queue를 반환합니다.

3. S초 동안 BFS 반복

• S번 동안 BFS(queue) 함수를 호출하여 바이러스 증식을 시뮬레이션합니다.
• 각 초마다 queue는 BFS 함수가 반환한 new_queue로 갱신됩니다.
• 만약 더 이상 증식할 바이러스가 없으면(queue가 비어있으면), 반복문을 종료합니다.

4. 결과 출력

• S초 후 graph[nx-1][ny-1] 값을 출력합니다. (좌표는 1부터 시작하므로 인덱스 접근 시 1을 빼줍니다.)

⏱복잡도 분석

• 시간 복잡도: O(S * N^2). BFS는 최악의 경우 모든 칸을 방문할 수 있으므로 O(N^2)의 시간이 걸립니다. 이를 S번 반복하므로 전체 시간 복잡도는 O(S * N^2)입니다. 바이러스를 정렬하는 데 O(K log K) 시간이 걸리지만, K <= 1000이므로 N^2에 비해 무시할 수 있습니다.
• 공간 복잡도: O(N^2). graph 리스트가 N x N 크기를 가지므로 O(N^2)의 공간을 사용합니다. queue도 최악의 경우 모든 칸에 바이러스가 있을 수 있으므로 O(N^2)의 공간을 사용할 수 있습니다.

핵심 포인트

1. BFS 활용: 바이러스의 증식은 동시에 일어나고, 번호가 낮은 바이러스부터 증식해야 하므로 BFS를 사용하여 효율적으로 시뮬레이션할 수 있습니다.
2. 바이러스 번호 순서: 바이러스 번호가 낮은 순서대로 증식하도록 초기 큐를 정렬하는 것이 중요합니다.
3. 방문 여부 확인: 이미 바이러스가 존재하는 칸에는 다른 바이러스가 들어갈 수 없으므로, 방문 여부를 확인하는 과정이 필수적입니다. graph[sx][sy] == 0 조건을 통해 이를 구현합니다.

풀이 코드

import sys
from collections import deque

input = sys.stdin.readline

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


graph = []

for i in range(n):
    graph.append(list(map(int,input().split())))

queue = []
for i in range(n):
    for j in range(n):
        if graph[i][j] != 0:
            queue.append((graph[i][j],i,j))

queue.sort()
queue = deque(queue)

s,nx,ny= map(int,input().split())
directions = [(1,0),(-1,0),(0,1),(0,-1)]
def BFS(queue):
    new_queue = deque()
    while queue:
        virus,x,y = queue.popleft()

        for dx,dy in directions:
            sx,sy = x+dx, y+dy
            if 0<= sx < n and 0<= sy < n and graph[sx][sy] == 0:
                graph[sx][sy] = virus
                new_queue.append((virus,sx,sy))

    return new_queue
for i in range(s):
    queue = BFS(queue)
    if not queue:
        break

print(graph[nx-1][ny-1])