백준 18405: 경쟁적 전염

1. 문제 설명

문제 링크

• 입력
  • 첫째 줄에 자연수 N, K가 공백을 기준으로 구분되어 주어짐
  • 둘째 줄부터 N개의 줄에 걸쳐서 시험관의 정보가 주어짐 : 존재하는 바이러스의 번호가 공백을 기준으로 주어짐, 단, 해당 위치에 바이러스가 존재하지 않는 경우 0이 주어짐 ( 모든 바이러스의 번호는 K이하의 자연수)
  • N+2번째 줄에는 S, X, Y가 공백을 기준으로 구분되어 주어짐
• 출력 : S초 뒤에 (X,Y)에 존재하는 바이러스의 종류를 출력, 만약 S초 뒤에 해당 위치에 바이러스가 존재하지 않는다면, 0을 출력

import sys
from collections import deque

input = sys.stdin.readline

# 4방향 탐색
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]


def bfs(a, b):
    queue = deque()
    queue.append((a, b))

    while queue:
        x, y = queue.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]

            # 범위를 벗어 나지 않고 전염이 이루어지지 않은 곳이라면
            if 0 <= nx < n and 0 <= ny < n and not maps[nx][ny]:
                # 해당 바이러스 값으로 전염
                maps[nx][ny] = maps[a][b]

                # 지속적으로 전염된 위치 값 추가
                posit.append([maps[a][b], nx, ny])


# 바이러스 위치 를 위한 리스트
posit = []

# 그래프 리스트
maps = []

n, k = map(int, input().split())
for i in range(n):
    a = list(map(int, input().split()))
    for j in range(n):
        # 바이러스 라면
        if a[j]:
            # 위치 값 넣어주기
            posit.append([a[j], i, j])
    maps.append(a)
s, x, y = map(int, input().split())

# 바이러스 값 기준으로 낮은 값부터 전염 이기때문에 sort 진행
posit.sort()

# 초 만큼 반복문
for _ in range(s):
    # 추가 되는 바이러스 길이에 맞춰 반복문 진행
    for i in range(len(posit)):

        # 해당 바이러스가 전염이 이루어 진것이 아니라면
        if posit[i][0]:
            # 바이러스 전염 진행
            bfs(posit[i][1], posit[i][2])

            # 전염 이후에는 전염성 제로로 만들기
            posit[i][0] = 0

# 출력문
if maps[x - 1][y - 1]:
    print(maps[x - 1][y - 1])
else:
    print(0)

3. 회고

Q. 문제를 보고 든 생각

• 전형적인 BFS 문제이다 (단순하게 BFS로 풀어 내면 될 것 같았다.)
• 문제 내에 있는 시간제한 만큼만 돌려야 하는데 어떻게 돌려야 하지??? -> (그냥 단순하게 주어진 시간 만큼만 돌리면 되는 문제 였다. 간단하게 해결!!)

4. 고쳐야 할점

해당 바이러스가 전염이 이루어 진것 인지 아닌지 판별 해주는 코드가 시간을 많이 잡아 먹는 코드인거 같다.(필자는 pypy3로 체출했음에도 1520ms 가 나왔다.)

이를 고치기 위해서는 어떻게 코드를 작성해야 할지 고민을 하면 될것 같다!!