알고리즘 스터디 - 백준 18405번 : 경쟁적 전염

문제 해석

• NxN 크기의 시험관 내에 1~K까지의 바이러스 종류가 존재
• 매초마다 1 -> 2 -> ... -> K 순으로 상하좌우로 바이러스가 증식

제약 조건

1. 바이러스는 1보다 작고 n보다 큰 위치에 증식할 수 없다.
2. 바이러스는 다른 종류의 바이러스가 존재할 경우 증식할 수 없다.

• 예상되는 어려움 : 바이러스가 순서대로 증식하려면 각 바이러스마다의 위치를 기록해놔야함

입력 순서

1. N, K 입력 받음
2. NxN의 시험관 입력 받음 <- 여기서 각 바이러스의 위치를 기록해놓자.
3. S, X, Y로 S초 일 때 X, Y에 있는 바이러스의 종류 있으면 1~K, 없으면 0

알고리즘 코드

N, K = map(int, input().split())

virus = []
virus_position = dict()

for i in range(N):
    n_list = list(map(int, input().split()))
    virus.append(n_list)

    # 바이러스 위치 저장
    for j in range(N):
        if n_list[j] != 0:
            if n_list[j] in virus_position:
                virus_position[n_list[j]].append([j, i])
            else:
                virus_position[n_list[j]] = [[j, i]]

# 기존 x, y보다 1이 낮아야 함
s, x, y = map(int, input().split())

# 각 초마다 돌아야함
for _ in range(s):
    # 크기 오름차순으로 정렬
    sort_virus_position = sorted(virus_position.items(), key=lambda x: x[0])
    new_virus = dict()

    # 각 바이러스 마다 돌아야함
    for key, val in sort_virus_position:
        # 상하좌우
        dx = [0, 0, 1, -1]
        dy = [1, -1, 0, 0]
        for current_x, current_y in val:
            for m in range(4):
                new_x = current_x + dx[m]
                new_y = current_y + dy[m]
                if new_x >= 0 and new_x < N and new_y >= 0 and new_y < N and virus[new_y][new_x] == 0:
                    virus[new_y][new_x] = key
                    if key in new_virus:
                        new_virus[key].append([new_x, new_y])
                    else:
                        new_virus[key] = [[new_x, new_y]]
    
    virus_position = new_virus

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

• 기본적으로 BFS가 행렬 위에서 움직이는 방식을 적용한 것을 응용하였다.

주의할 점

1. 바이러스 순서를 정렬해주어야 한다.
2. 새로운 바이러스 딕셔너리를 설정해주지 않으면 계속 확장된 1이 또 돌아가는 불상사가 발생하게 되어 1만 나타나는 결과가 나온다.