백준 18405 - 파이썬

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

18405번: 경쟁적 전염

문제 풀이

BFS를 이용하여 풀려고 하였고, 처음에 바이러스가 존재하는 위치를 큐에 담아준 뒤, 큐에 있는 바이러스를 기준으로 BFS 탐색을 시작하였다. 그러기 위해서 4중 반복문을 사용하였는데, 정답 도출은 가능했다. 하지만 4중 반복문을 사용한 시점부터 이미 시간초과가 날 것을 알고 있었고, 결국 시간초과가 났다.

 

내가 푼 풀이

import sys
from collections import deque
input = sys.stdin.readline

n, k = map(int, input().split())
graph = [list(map(int, input().split())) for _ in range(1, n + 1)]
visited = [[False] * (n) for _ in range(n)]

second, x, y = map(int , input().split())

q = deque()

def bfs():

  dx = [-1, 1, 0, 0]
  dy = [0, 0, -1, 1]

  while q:
    x, y = q.popleft()

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

      if nx < 0 or nx >= n or ny < 0 or ny >= n:
        continue

      if graph[nx][ny] == 0 and not visited[nx][ny]:
        graph[nx][ny] = graph[x][y]
        visited[nx][ny] == True

virus_list = [i for i in range(1, k + 1)]
result = 0

for time in range(second):
  for virus_num in virus_list:
    for i in range(n):
      for j in range(n):
        if graph[i][j] == virus_num and not visited[i][j]:
          q.append((i, j))
          visited[i][j] = True

  bfs()
  
print(graph[x-1][y-1])

다른 방법이 뭐가 있을까 고민하다가 결국 답을 찾아보기로 하였고, <이것이 코딩 테스트다>에서 참고하였다.

 

<이코테>

from collections import deque
import sys
input = sys.stdin.readline

n,k = map(int, input().split())
graph = []
data = [] 
for i in range(n):
    graph.append(list(map(int, input().split())))
    for j in range(n):
        if graph[i][j] !=0:
            data.append((graph[i][j],0,i,j))

data.sort()
q = deque(data)

target_s, target_x, target_y = map(int, input().split()) 

dx = [0, 0, -1, 1]
dy = [1, -1, 0, 0]

while q:
    virus, s, x, y = q.popleft()
    if s == target_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:
                graph[nx][ny] = virus
                q.append((virus, s+1, nx,ny))

print(graph[target_x -1][target_y -1])

여기서는 처음에 입력 값을 받을 때 0이 아닌 숫자들은 전부 바이러스이기에 바로 리스트에 추가를 해줬다. 또한 리스트에 추가할때 바이러스의 종류, 시간, 위치를 입력해뒀다. 이를 BFS 탐색을 할 때 활용하였다.

 

이 문제를 풀면서 느낀 점은 문제를 푸는 방법은 정말 여러가지가 있고, 이를 얼마나 효율적으로 풀어낼지도 정말 다양한 방법이 존재한다는 것이다. 어찌보면 당연한 말이지만 막상 문제를 풀때는 내가 푼 한가지 방법 말고는 크게 다른 방법이 떠오르지 않는다는 점이다. 꾸준히 노력하는 수밖에 없겠지만 여러가지 방법들을 습득하고 활용하여 효율적으로 풀 수 있도록 해야 되겠다.