백준 - 14502 바이러스 풀이

풀이방법

완전탐색 유형 문제입니다. 총 4단계로 문제를 풀 수 있습니다. 완전 탐색은 2단계인 바이러스 전파에서 진행됩니다. 이 문제의 핵심은 완전탐색을 하기 전에 벽을 생성하고, 영역 계산후 벽을 제거하여 원래 상태로 되돌리는 것입니다.

1️⃣ 벽 생성

2️⃣ 바이러스 전파

3️⃣ 최대 영역 계산

4️⃣ 벽 제거

 

코드

1️⃣ 벽을 생성하기 위해 벽이 생성될 수 있는 위치를 조합으로 계산합니다. 위치를 계산하기 전에 바이러스 위치와 아무것도 없는 위치를 구해야합니다.

from collections import deque
from itertools import combinations

# 바이러스와 벽이 있는 위치 계산 
graph = M * N
virus = deque()
empty = []
if graph[row][col] == 2:
  virus.append((row, col))
elif graph[row][col] == 0:
  empty.append((row, col))

# 벽 생성
for p in combinations(empty, 3):
  one, two, three = p
  
  # 벽 생성
  graph[one[0]][one[1]] = 1
  graph[two[0]][two[1]] = 1
  graph[three[0]][three[1]] = 1

  바이러스 전파 코드 ...
  영역계산 코드 ...

  # 벽 제거
  graph[one[0]][one[1]] = 0
  graph[two[0]][two[1]] = 0
  graph[three[0]][three[1]] = 0

 

2️⃣ 바이러스 전파는 bfs를 사용했습니다. 바이러스 전파 이후 최대 영역을 계산합니다.

for p in combinations(empty, 3):
  벽 생성 코드 ...
  
  # 바이러스 전파
  queue = virus.copy()
  while queue:
      row, col = queue.popleft()

      for i in range(4):
          tx = row + dx[i]
          ty = col + dy[i]

          if tx < 0 or tx >= M or ty < 0 or ty >= N: continue
          if graph[tx][ty] == 0 and visited[tx][ty] == False:
              visited[tx][ty] = True
              queue.append([tx, ty])

  # 영역 계산
  safe_area = 0
  for i in range(M):
      for j in range(N):
          if graph[i][j] == 0 and visited[i][j] == False:
              safe_area += 1

  # 최대 영역 계싼
  answer = max(answer, safe_area)
 
  벽 제거 코드

 

전체코드

# 어떻게 무식하게 풀지?
# 벽을 만든다.
# 벽을 해제한다.

import sys
from itertools import combinations
from collections import deque

_input = sys.stdin.readline

M, N = map(int, _input().rstrip().split())
graph = [list(map(int, _input().rstrip().split())) for _ in range(M)]

virus = deque()
empty = []

for i in range(M):
    for j in range(N):
        if graph[i][j] == 2:
            virus.append([i, j])
        elif graph[i][j] == 1:
            pass
        else:
            empty.append([i, j])

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

for p in combinations(empty, 3):
    one, two, three = p

    # 벽 만들기
    graph[one[0]][one[1]] = 1
    graph[two[0]][two[1]] = 1
    graph[three[0]][three[1]] = 1

    visited = [[False] * N for _ in range(M)]
    for v in virus:
        visited[v[0]][v[1]] = True

    # 바이러스 전파
    queue = virus.copy()
    while queue:
        row, col = queue.popleft()

        for i in range(4):
            tx = row + dx[i]
            ty = col + dy[i]

            if tx < 0 or tx >= M or ty < 0 or ty >= N: continue
            if graph[tx][ty] == 0 and visited[tx][ty] == False:
                visited[tx][ty] = True
                queue.append([tx, ty])

    safe_area = 0
    for i in range(M):
        for j in range(N):
            if graph[i][j] == 0 and visited[i][j] == False:
                safe_area += 1

    answer = max(answer, safe_area)

    graph[one[0]][one[1]] = 0
    graph[two[0]][two[1]] = 0
    graph[three[0]][three[1]] = 0

print(answer)

 

참고자료

https://velog.io/@jaenny/백준-14502-연구소-파이썬python