[Python] 백준 알고리즘 18405 - 경쟁적 전염

[Python] 백준 알고리즘 18405 - 경쟁적 전염 

 

18405번: 경쟁적 전염 (acmicpc.net)

18405번: 경쟁적 전염

 

경쟁적 전염 문제 페이지

 

풀이 과정

 문제에서 입력하는 값

 

• n, k  /  실험관의 크기와 바이러스의 종류
• 시험관
• s, ( x , y ) / 실험 시간과 실험 후 추출하고자 하는 좌표

 

사용 개념

 

• 우선순위 큐, 덱
• 너비 우선 탐색
• 그래프 

풀이 접근방법

 

• 문제에 해당하는 입력값을 입력받는다
• 실험관에서 바이러스의 종류(vn), 해당 바이러스의 위치(x, y), 실험 시간(depth) 입력받아서 리스트에 입력
  • 바이러스의 경우 1번부터 진행해서 n번까지의 차례대로 리스트에서 나와야 함
  • sort() 사용으로 정렬
  • 주어진 리스트를 덱으로 변경해서 넣어주기 
• BFS - 너비 우선 탐색 사용
  • 멈추는 조건은 s가 될 때까지 반복, 즉  반복의 횟수가 s가 되는 경우
    • 주어진 depth가 s와 같아진다면 멈추기(if문 : break) 
  • 방향의 이동은 dx , dy = [ 1 , 0 , -1 , 0]  ,  [0 , 1 , 0 , -1]과 for 반복문을 통해 상하좌우 탐색
  • 상하좌우를 탐색하면서 해당 위치의 0이 존재하면 바이러스 종류(vn)를 넣어주기
    
    • 새로 바이러스가 심어진 위치와 종류 그리고 한 번의 반복이 진행되었다는 변수 덱에 넣어주기
    • que.append(vn, nx, ny, depth+1)
• 문제에서 요구한 값 출력

 

풀이 코드

from collections import deque
from queue import PriorityQueue

'''
경쟁적 감염
'''
n, k = map(int, input().rstrip().split())  # 그래프 크기와 바이러스의 종류
'''
그래프 입력
map 변수를 통해 input으로 입력받은 값들을 int형으로 변환 후 리스트로 변경 및 반복문을 통해 이중리스트 만듬
만들어진 이중리스트는 문제에서 요하는 실험관의 지도
'''
graph = [list(map(int, input().rstrip().split())) for _ in range(n)]
s, ox, oy = map(int, input().split())  # 문제에서 요구한 s(시간) / x,y (요구위치)

# 방향이동을 위한 방향표
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]

# 데이터 담을 리스트 선언
data = []

for i in range(0, n):
    for j in range(0, n):
        if graph[i][j] != 0:  # 그래프 탐색에서 그래프의 원소가 0이 아닐경우
            data.append((graph[i][j], i, j, 0))  # 우선순위 큐에 바이러스 종류 , 위치, 그리고 시간초를 체크를 위한 depth를 넣어준다

data.sort()
que = deque(data)

while que:
    vn, x, y, depth = que.popleft()

    if depth == s :
        break

    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if 0 <= nx < n and 0 <= ny < n:
            if graph[nx][ny] != 0:
                continue
            else:
                graph[nx][ny] = vn
                que.append((vn, nx, ny, depth + 1))

print(graph[ox - 1][oy - 1])  # 문제의 답 출력 이 때 그래프의 인덱스는 실제로 0부터이므로 요구위치값에서 -1인 부분을 출력

 

 

고찰

 

처음 문제를 접근할 때 문제의 경우 바이러스의 종류가 낮은 순서로 진행이 되어야 한다는 점에서 우선순위 큐를 사용했었다. 다만 우선순위 큐를 사용하니 나중에 1번의 바이러스가 들어와도 낮은 값으로 정렬을 하여 그 1번이 먼저 앞으로 와서 공간을 1로 채우는 경우가 발생하였습니다. 그래서 그 후 코드를 우선순위 큐가 아닌 기본 리스트와 덱으로 사용하여 다시 풀었고 답을 도출할 수 있었습니다. 문제를 풀면서 코드에 맞게 자료구조를 정하는 것에 중요성을 느꼈습니다