[Algorithm] 14502. 연구소

14502: 연구소(완탐 + BFS)

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

• 문제 티어 : G4
• 풀이 여부 : Solved
• 소요 시간 : 31:42

정답 코드

import sys
from itertools import combinations
from collections import deque
from copy import deepcopy
input = sys.stdin.readline

# 바이러스 전파 bfs
def bfs(arr):
    dx, dy = (-1, 1, 0, 0), (0, 0, -1, 1)
    for x in range(N):
        for y in range(M):
            if arr[x][y] == 2:  # 바이러스인 경우
                dq = deque([(x, y)])
                while dq:
                    cx, cy = dq.popleft()
                    for i in range(4):
                        nx, ny = cx + dx[i], cy + dy[i]
                        if 0 <= nx < N and 0 <= ny < M and arr[nx][ny] == 0:
                            arr[nx][ny] = 2  # 바이러스 전파
                            dq.append((nx, ny))

    return sum(row.count(0) for row in arr)  # 안전 영역 계산

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

zero_idx = []
for i in range(N):
  for j in range(M):
    if arr[i][j] == 0:
      zero_idx.append((i, j))

safe_max = 0
for walls in combinations(zero_idx, 3): # 3개의 벽 세우기
    modified_arr = deepcopy(arr)
    for x, y in walls:
        modified_arr[x][y] = 1  # 벽 세우기
    safe_max = max(safe_max, bfs(modified_arr))  # 안전 영역의 최댓값 갱신

print(safe_max)

접근 방식

문제에 대한 사고 흐름은 다음과 같았다.

1. 0의 좌표 중 3군데를 무작위로 고르기
2. 3군데의 값을 1로 만들어, 3개의 벽을 추가로 설치
3. BFS를 통해 2(바이러스)의 값을 가진 인덱스를 큐에 넣어, 바이러스 전파
4. 바이러스 전파 이후, 안전 영역의 값 리턴
5. 안전영역의 최댓값 갱신

zero_idx = []
for i in range(N):
  for j in range(M):
    if arr[i][j] == 0:
      zero_idx.append((i, j))

다음과 같이 0의 좌표를 저장한다.
(리스트 컴프리헨션을 사용하는게 코드가 더 깔끔했겠지만!)

safe_max = 0
for walls in combinations(zero_idx, 3): # 3개의 벽 세우기
    modified_arr = deepcopy(arr)
    for x, y in walls:
        modified_arr[x][y] = 1  # 벽 세우기
    safe_max = max(safe_max, bfs(modified_arr))  # 안전 영역의 최댓값 갱신

다음 itertools의 combinations을 사용해 zero_idx로부터 3개의 벽을 세워줬다.
3개의 벽을 세우는 모든 방법에 대해 최대 안전 영역을 구해야하므로, deepcopy를 사용해 원본 배열을 복사해 사용했다.
combinations로 뽑아낸 3개의 인덱스 값을 1로 채워준 뒤, bfs 함수의 arr 인자로 전달한다.

# 바이러스 전파 bfs
def bfs(arr):
    dx, dy = (-1, 1, 0, 0), (0, 0, -1, 1)
    for x in range(N):
        for y in range(M):
            if arr[x][y] == 2:  # 바이러스인 경우
                dq = deque([(x, y)])
                while dq:
                    cx, cy = dq.popleft()
                    for i in range(4):
                        nx, ny = cx + dx[i], cy + dy[i]
                        if 0 <= nx < N and 0 <= ny < M and arr[nx][ny] == 0:
                            arr[nx][ny] = 2  # 바이러스 전파
                            dq.append((nx, ny))

    return sum(row.count(0) for row in arr)  # 안전 영역 계산

• 벽을 만드는 경우 → 무작위로 3개의 벽을 세우는 경우의 수를 만들기에 브루트포스 사용
• 바이러스를 전파시키는 경우 → 상하좌우로 이동하기에 BFS 사용

배열을 순회하며 2의 값을 가지는 인덱스의 x, y 좌표를 큐에 넣어준다.
이 때 통상적인 BFS와의 다른 점은, 방문했던 좌표에 다시 방문하면 안되는 제약이 없으므로 visited배열 없이 사용한다.

바이러스의 전파가 완료되면 arr의 값을 2로 갱신해준 뒤, 큐에 있는 모든 좌표를 다 순회해 루프를 빠져나오면, 0의 값을 리턴해준다.

배운점 또는 느낀점

BFS와 브루트포스를 기반으로 생각할 거리가 많았던 문제지만, 접근하기는 수월한 편이었던 것 같다!

visited가 BFS에 무조건 필요한 것은 아니라는 점!