popeye0618

Backend Developer

[python] 백준 - 17142 (연구소 3)

ko 0 조회수 시리즈 · 알고리즘 #알고리즘

골드3 문제이며, 제한 시간은 python3: 1.5초, pypy3: 0.5초이다.

문제

해결 과정

문제에 들어오자마자 제한 시간이 짧은걸 보고, 시간 복잡도가 중요하겠구나 싶었다. 따라서 14502번 연구소를 풀 때보다 코드의 성능을 좋게 만들어야겠다고 생각했다. 해결한 방법은

  1. 입력받은 값중 바이러스의 위치를 모두 저장해놓는다.
  2. 조합을 사용해 m개의 바이러스가 활성화 된 모든 경우를 구한다.
  3. 그 경우마다 bfs를 돌려서 바이러스를 퍼뜨리며, 최대 시간을 구한다.
  4. answer의 값이 바뀌었으면 그 값을 출력, 바뀌지 않았다면 -1을 출력한다.

풀이

py
from collections import deque
from itertools import combinations

def bfs(v):
  visited = [[-1 for _ in range(n)] for _ in range(n)]
  queue = deque(v)
  for x, y in v:
    visited[x][y] = 0
  
  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 visited[nx][ny] == -1 and graph[nx][ny] != 1:
        visited[nx][ny] = visited[x][y] + 1
        queue.append((nx, ny))

  max_value = 0
  for i in range(n):
    for j in range(n):
      if graph[i][j] == 0:
        if visited[i][j] == -1:
          return -1
        max_value = max(max_value, visited[i][j])
  return max_value

n, m = map(int, input().split())
graph = []
for _ in range(n):
  graph.append(list(map(int, input().split())))
  
virus = []
for i in range(n):
  for j in range(n):
    if graph[i][j] == 2:
      virus.append((i, j))
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
answer = 2501
for c in combinations(virus, m):
  result = bfs(c)
  if result != -1:
    answer = min(answer, result)
print(answer) if answer != 2501 else print(-1)

시간 복잡도

시간 복잡도를 줄이는 아이디어가 3가지 존재한다.

  1. 조합을 사용해서 정해진 경우만 bfs돌리기
  2. 바이러스를 퍼뜨릴 때, 그리드에 변화를 주지 않고 visited 리스트로만 퍼뜨린다.
  3. 바이러스가 퍼지지 않는 공간이 존재할 경우 즉시 -1을 리턴한다.

괜찮은 문제였던 것 같다!

댓글

0

아직 댓글이 없습니다.

댓글 쓰기