[백준][Python]14502번(연구소)

백준 14502번

✔️ 문제 풀이

• BFS로 풀어야함을 알고 있지만 문제를 풀면서도 시간초과에 대한 두려움이 엄습해옴..
• 쓰읍.. 이거 시간초과 날거같은데... 이거 시간초관데...
• 근데 웬걸 시간초과 없이 한 번에 통과! 대박

.

◾대략적인 그림

1) 먼저 빈 칸에 벽을 세우는 과정 필요
◽ 비어있는 칸들을 리스트에 넣고, 그 중에 순서 상관없이 3개의 원소를 뽑는다
2) 벽이 3개 세워진 각각의 케이스에 대해 안전구역을 구해야함
◽ 이때 bfs 활용

◾변수 선언

• 처음 입력된 지도에서 벽의 개수, 바이러스의 개수를 입력받는다,
  ⇒ wall_number, virus_number: 안전구역 개수를 카운트할 때 편리
• 바이러스 개수를 카운트해주면서 바이러스 좌표도 저장,
  ⇒ virus: 바이러스 퍼뜨릴 때 사용
• 비어있는 곳의 좌표 저장
  ⇒ empty_map: 벽을 세울 좌표를 정하기 위해

.

◾벽 세우기(combinations 사용)

• empty_map과 벽의 개수 3을 인수로 넣고 반환되는 벽의 좌표들을 walls로 받음
• 각각의 walls에 대해서 바이러스 퍼뜨리기 수행하려면 원본 지도인 original_map과 바이러스의 좌표를 갖고 있는 virus를 복사하여 준비해야함
  ⇒ 각 케이스마다 이 두 개가 꼭 필요하고, 변경되지 않은 상태로 다음 케이스도 이용해야 하기 때문에
• walls의 좌표대로 original_map의 복사본인 omap에 벽을 세워준다
  ⇒ 해당 좌표의 원소값을 1로 변경

.

◾바이러스 퍼뜨리기(bfs 활용)

• virus의 복사본인 vlocation을 queue로 활용
• 원소값이 2인 좌표의 상하좌우의 인덱스를 검사하고, 인덱스 범위 내일 경우 0인 경우 해당 값을 2로 바꿔준다
  ⇒ 바이러스가 퍼진것임으로 local_virus 값을 1 증가시킨다

.

◾안전한 장소 카운트

• 전체 넓이(n*m)에서 벽의 개수(wall_number + 3)와 각 loop에서의 바이러스 개수인 (local_virus)을 빼주면 안전한 장소의 개수가 카운트된다

최종 제출 코드

from collections import deque
from itertools import combinations
import sys
import copy

input = sys.stdin.readline

n, m = map(int, input().split())
count = n*m
wall_number = 0
virus_number = 0

original_map = []
virus = deque()
empty_map = []

# 지도를 입력받는 것이 주목적
# - 추가로 바이러스(원소값이 2)의 좌표와 개수,
# - 빈 공간(원소값이 0)의 좌표,
# - 벽(원소값이 1)의 개수를 저장한다
for i in range(n):
  row = list(map(int, input().split()))
  for j in range(len(row)):
    if row[j] == 2:
      virus.append([i, j])
      virus_number += 1
    elif row[j] == 0:
      empty_map.append([i, j])
    else:
      wall_number += 1
  original_map.append(row)


def bfs(original_map, virus):

  global wall_number, virus_number, count

  # 전체 케이스 각각의 도출값에서 결과값을 가리기 위한 변수
  result = 0
  dx = [-1, 1, 0, 0]
  dy = [0, 0, -1, 1]

  # empty 배열을 활용하여, 벽을 놓을 좌표 3개를 구한다
  for walls in combinations(empty, 3):

    # 지도와 바이러스 위치가 필요하지만 원본을 사용하면 다음 조합 케이스에 영향을 미침
    # copy를 이용하여 원본을 복사하여 사용한다
    omap = copy.deepcopy(original_map)
    vlocation = copy.copy(virus)

    # 이번 loop에서의 바이러스 개수를 구하기 위한 변수
    local_virus = virus_number

    # combinations가 생성한 조합에 따라 해당 좌표에 벽을 세운다
    for wall in walls:
      omap[wall[0]][wall[1]] = 1

    # 벽이 모두 세워졌으니 바이러스를 퍼트린다
    while vlocation:

      y, x = vlocation.popleft()

      # 바이러스는 앞뒤좌우로 퍼질수있다
      for i in range(4):
        nx = x+dx[i]
        ny = y+dy[i]
        if nx < 0 or ny < 0 or nx >= m or ny >= n:
          continue
        # 바이러스는 비어있는 곳에만 퍼질 수 있다
        # - 벽이 있는 곳은 안됨. 바이러스 있는 곳은 이미 퍼진 곳
        if not omap[ny][nx]:
          omap[ny][nx] = 2
          vlocation.append([ny, nx])
          # 바이러스 개수 증가
          local_virus += 1

    # 안전한 곳은 전체 넓이에서 벽들의 개수를 빼고 바이러스의 개수를 뺀 것과 같다
    # 이번 loop에서의 도출값이 result보다 크면 이 값으로 result를 업데이트
    result = max(result, count - wall_number-3 - local_virus)
    
  return result

print(bfs(original_map, virus))

✔️ 결과

• 시간도 생각보다 짧게 걸림ㅎㅎ