[백준] 18405. 경쟁적 전염 (python)

https://www.acmicpc.net/problem/18405

18405번: 경쟁적 전염

 

import sys
from collections import deque
n, k = map(int, sys.stdin.readline().split())
graph = [[0]*(n+1)]
vir = []
for i in range(1, n+1):
    graph.append([0] + list(map(int, sys.stdin.readline().split())))
    for j in range(1, n+1):
        if graph[i][j] > 0:
            vir.append([graph[i][j], i, j])
second, a, b = map(int, sys.stdin.readline().split())

visited = [[False]*(n+1) for _ in range(n+1)]
def bfs(x, y):
    # 1. 시작노드로 초기화 & 방문처리
    visited[x][y] = True
    dx = [-1, 0, 1, 0]
    dy = [0, 1, 0, -1]
    # 인접노드 탐색(상하좌우)
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        # 범위 확인
        if nx < 1 or nx > n or ny < 1 or ny > n:
            continue
        if visited[nx][ny]:
            continue
        # 공백이고 방문한 적 없으면 해당 바이러스 퍼트리기
        if graph[nx][ny] == 0:
            # 바이러스 정보 업데이트
            graph[nx][ny] = graph[x][y]
            vir.append([graph[nx][ny], nx, ny])
            # 해당 노드 방문처리
            visited[nx][ny] = True

for s in range(1, second+1):
    length = len(vir)
    # 1. 바이러스 숫자 낮은 순으로 정렬
    vir.sort()
    for v in range(length):
        # 2. 1초마다 숫자가 낮은 바이러스부터 상하좌우 퍼짐
        bfs(vir[v][1], vir[v][2])
    # 3. 퍼진 바이러스의 좌표들은 삭제(중복 계산 방지)
    for r in range(length):
        vir.remove(vir[0])

print(graph[a][b])

 

먼저 문제를 읽으면서 이건 BFS문제구나 하고 생각했다.

 

1. 바이러스 좌표를 저장한다.

2. s초까지 반복문을 돌리면서 1초마다 아래 3-5번을 진행

3. 바이러스 숫자가 낮은 순으로 정렬

4. 바이러스 좌표 하나씩 BFS 수행

5. BFS 수행한 바이러스 좌표 모두 제거(중복 계산을 방지하기 위해서)

6. (a,b)좌표의 값 출력

 

코드를 작성해서 예제의 값이 제대로 나오는 데까지는 얼마 걸리지 않았는데,

막상 백준에 제출해보니 시간초과가 계속났다.

 

그래서 5번의 과정을 추가했다.

사실 이 과정에서도 시행착오가 많았다.

바이러스 리스트의 크기만큼 반복문을 돌면서 BFS를 수행하는데

BFS를 수행하면서 전염된 바이러스의 좌표가 다시 바이러스 리스트에 추가되기 때문에

바이러스 리스트의 크기가 계속 변경되는 점 때문에 헷갈렸다.

 

처음에는 

    for v in range(len(vir)):
        # 2. 1초마다 숫자가 낮은 바이러스부터 상하좌우 퍼짐
        bfs(vir[v][1], vir[v][2])

위처럼 range안에 vir의 길이를 구하는 함수를 넣었기 때문에 BFS를 수행하면서 추가되는 바이러스의 좌표까지 계산이 되었고, 문제에서 주어진 설명처럼 1초마다 바이러스가 상하좌우로 한 칸씩 이동하는 방식으로 진행되지 않았다.

그리고 바이러스가 추가되면서 계산이 이미 되었는데 다음 s로 넘어갔을 때 같은 바이러스 좌표에 대해서 각각 한 번씩 다시 수행이 되기 때문에 중복되는 계산이 아주 많았던 것 같다.

그래서 결과적으로 답은 나오는데 시간 초과가 계속 나오지 않았나 싶다.

 

그래서 1초가 시작될 때 저장되어 있는 바이러스의 개수를 저장해 그만큼만 반복문을 돌리고,

다음 2초가 시작되기 전에 이미 BFS를 수행한 바이러스의 좌표는 삭제한 뒤에

새롭게 추가된 바이러스의 개수를 계산하고 정렬한 다음

다시 그만큼만 반복문을 돌리는 방식으로 아래와 같이 수정하였다.

for s in range(1, second+1):
    length = len(vir)
    # 1. 바이러스 숫자 낮은 순으로 정렬
    vir.sort()
    for v in range(length):
        # 2. 1초마다 숫자가 낮은 바이러스부터 상하좌우 퍼짐
        bfs(vir[v][1], vir[v][2])
    # 3. 퍼진 바이러스의 좌표들은 삭제(중복 계산 방지)
    for r in range(length):
        vir.remove(vir[0])

 

이렇게 함으로써 중복 계산이 줄어들고, 1초에 바이러스가 상하좌우로 한 칸씩만 퍼지게 된다.

 

 

허허... 시간 초과 틀렸습니다 파티다..

왜 시간 초과가 계속 나오는지 생각해보면서

바이러스를 저장하는 자료구조를 우선순위 큐로도 바꿔보고, 큐로도 바꿔보고, 

정렬을 하지 않고 BFS에서 숫자가 낮은 바이러스가 퍼지도록 처리하는 방법이 없나 고민해보기도 하면서

꽤나 많은 시행착오가 있었다.

 

이 문제를 풀면서 BFS를 떠올리고 어떻게 풀지 순서를 정리하는 것까지는 어렵지 않았는데,

실제로 코드를 작성하면서 시간 초과가 나지 않게끔 중복 계산을 없애면서 효율적으로 코드를 짜는 것과

문제설명에 부합하도록 디테일을 살피는 것도 중요하다는 것을 다시금 깨달았다.

 

알고리즘 분류

• BFS
• 구현