[Baekjoon] 18405번: 경쟁적 전염 (DFS/BFS Gold5) - Python

1. 문제

---

경쟁적 전염

2. 풀이

---

코드

from collections import deque

def solution():
    n, k = map(int, input().split())
    grid = [list(map(int, input().split())) for _ in range(n)]
    target_s, target_x, target_y = map(int, input().split())
    queue = deque()

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

    while queue:
        current_x, current_y, current_virus, time = queue.popleft()
        if time == target_s:
            break

        for dx, dy in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
            new_x, new_y = current_x + dx, current_y + dy
            if 0 <= new_x < n and 0 <= new_y < n and grid[new_x][new_y] == 0:
                grid[new_x][new_y] = current_virus
                queue.append((new_x, new_y, current_virus, time + 1))

    return grid[target_x-1][target_y-1]

print(solution())

입력 및 출력

3 3
1 0 2
0 0 0
3 0 0
2 3 2

>> 3

3. 로직

---

1. 첫째 줄에서 n과 k를 입력받는다. n은 시험관의 크기이고, k는 바이러스의 종류 수이다.

2. 둘째 줄부터 n개의 줄에 걸쳐서 시험관의 정보를 입력받는다. 0은 빈 칸을 의미하고, 1부터 k까지의 숫자는 해당 바이러스의 번호를 의미한다.

3. 마지막 줄에서는 목표 시간(target_s), 목표 위치의 x좌표(target_x), y좌표(target_y)를 입력받는다.

4. 큐(queue)를 생성하고, 시험관을 순회하며 초기 바이러스의 위치를 큐에 추가한다. 큐에는 위치 (x, y), 바이러스 번호, 시간 정보를 함께 저장한다.

5. 큐가 비어있을 때까지 다음 작업을 반복한다.

• 큐에서 원소를 하나 꺼내온다. 현재 위치 (current_x, current_y), 현재 바이러스 번호(current_virus), 시간(time)을 얻는다.
• 현재 시간(time)이 목표 시간(target_s)와 같다면 반복을 종료한다.
• 상하좌우로 인접한 위치(new_x, new_y)를 계산한다.
• 인접한 위치가 시험관 내부에 있고, 빈 칸(0)인 경우에만 바이러스를 전파한다.
• 전파된 바이러스 번호를 해당 위치에 기록하고, 큐에 새로운 위치와 시간 정보를 추가한다.

6. 목표 위치(target_x, target_y)에 해당하는 시험관의 상태를 반환한다.