18405. 경쟁적 전염 [BAEKJOON / Python]

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

 

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

 

시험관의 크기와 바이러스의 위치 정보가 주어졌을 때, S초가 지난 후에 (X,Y)에 존재하는 바이러스의 종류를 출력하는 프로그램을 작성하시오.

input = 3 3
             1 0 2
             0 0 0
             3 0 0
             2 3 2

output = 3

 

전체 코드

# 경쟁적 전염

from collections import deque

# 시험관 크키, 바이러스 종류 개수
n, k = map(int, input().split())   
maps = [list(map(int, input().split())) for _ in range(n)]

# 시간, 좌표 위치
s, x, y = map(int, input().split())

# maps 인덱스는 0부터 시작하기 때문
x = x -1
y = y - 1

now = []
for i in range(n):
    for j in range(n):
        if maps[i][j] != 0:
                    # 바이러스 번호, 바이러스 위치, 시간
            now.append((maps[i][j], i , j , 0)) # 튜플 형식으로 할당

now = deque(sorted(now))  # 바이러스 번호 정렬
                          # 1, 2, 3 순서로 바이러스가 확장해야 하기 때문에
# 우 좌 하 상
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]

while now:
    num, a, b, sec = now.popleft()

    if sec == s:    # 조건 시간이 되면 멈춘다
        break

    for i in range(4):
        nx = a + dx[i]
        ny = b + dy[i]

        if 0 <= nx < n and 0 <= ny < n:
            if maps[nx][ny] == 0:
                maps[nx][ny] = num 
                now.append((num, nx, ny, sec + 1))

print(maps[x][y])

 

 

문제 풀이 포인트

• BFS
• 바이러스의 번호 순으로 정렬

     ▶️ 바이러스 번호 순으로 증식되기 때문에!

 

 

코드 디테일

x, y값 1 빼주기

# 시험관 크키, 바이러스 종류 개수
n, k = map(int, input().split())   
maps = [list(map(int, input().split())) for _ in range(n)]

# 시간, 좌표 위치
s, x, y = map(int, input().split())

# maps 인덱스는 0부터 시작하기 때문
x = x -1
y = y - 1

각 변수에 입력값을 받는다. 

이때 x, y 변수에 받은 값으로 maps 좌표에서의 해당 바이러스 번호를 출력하게 된다. 

입력받은 값은 (1, 1)부터 시작되는 기준이지만, 코드 상에서 maps는 (0, 0)부터 시작되는 기준이므로

각 x, y의 값을 1씩 빼준다.

 

 

바이러스가 존재하는 좌표 순회

now = []
for i in range(n):
    for j in range(n):
        if maps[i][j] != 0:
                    # 바이러스 번호, 바이러스 위치, 시간
            now.append((maps[i][j], i , j , 0)) # 튜플 형식으로 할당

now = deque(sorted(now))  # 바이러스 번호 정렬
                          # 1, 2, 3 순서로 바이러스가 확장해야 하기 때문에

maps 좌표를 모두 순회하며 바이러스가 있는 좌표를 찾아낸다.

바이러스 번호(maps[i][j]), 바이러스 위치(i, j), 시간(0 (추후 while문 1회 반복 마다 추가되는 시간)) 정보를 now 변수에 넣어준다. 

1 0 2
0 0 0
3 0 0

만약 이러한 좌표가 주어지고 now에 값이 할당된다면

now = [(1, 0, 0, 0), (2, 0, 2, 0), (3, 2, 0, 0)]

이러한 형태이다.

 

이때 중요한 것은 바이러스 번호 기준으로 정렬을 해주어야 한다.

그 이유는 바이러스는 '번호가 낮은 종류의 바이러스부터 먼저 증식' 하기 때문이다.

1부터 3까지 오름차순으로 정렬하여 순서대로 증식하도록 해준다.

 

# 우 좌 하 상
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]

while now:
    num, a, b, sec = now.popleft()

    if sec == s:    # 조건 시간이 되면 멈춘다
        break

    for i in range(4):
        nx = a + dx[i]
        ny = b + dy[i]

        if 0 <= nx < n and 0 <= ny < n:
            if maps[nx][ny] == 0:
                maps[nx][ny] = num 
                now.append((num, nx, ny, sec + 1))

print(maps[x][y])

dx, dy에 4방향을 탐색하도록 값을 넣어준다.

 

while문으로 now가 모두 빌 때 까지 반복해준다.

now에 들어가있는 값을 차례대로 num, a, b, sec에 할당한다.

num , a, b, sec = 1, 0, 0, 0

그렇다면 현재 now의 제일 왼쪽에 있는 값 묶음이 각 변수에 들어가게 된다.

 

if sec == s: 를 통해 입력값으로 받은 주어진 시간이 되면 반복문을 멈추고 출력하도록 한다.

 

nx, ny에 4방향을 탐색할 수 있도록 값을 할당해준다.

 

        if 0 <= nx < n and 0 <= ny < n:
            if maps[nx][ny] == 0:
                maps[nx][ny] = num 
                now.append((num, nx, ny, sec + 1))

첫번째 if문으로 좌표 범위를 넘지 않도록 설정하고,

maps 좌표에서 바이러스가 증식되지 않은 위치인 0의 값을 찾는다.

방문한 곳이 0이라면 해당 위치에 바이러스 번호를 할당한 후

다시 해당 바이러스 번호와 새로운 위치(nx, ny) 그리고 1초를 더해준 후 now에 넣어준다.

 

방문한 위치가 0이 아닐 경우 해당 조건문이 성립되지 않으므로 now 리스트에 있는 다음 값인 바이러스 2번의 증식이 시작되는 것이다.