💻 백준 14502번: 연구소

문제 소개 🧐

N×M 크기의 연구소에 바이러스가 유출되었다. 연구소는 빈 칸(0), 벽(1), 바이러스(2)로 구성되어 있다. 바이러스는 상하좌우로 인접한 빈 칸으로 퍼져나간다.

새로 3개의 벽을 세워 바이러스의 확산을 막고, 바이러스가 퍼질 수 없는 ‘안전 영역’의 크기를 최대로 만드는 것이 목표다.

입력 📝

  • 첫째 줄: 지도의 세로 크기 N, 가로 크기 M (3 ≤ N, M ≤ 8)
  • 둘째 줄부터 N개의 줄: 지도의 모양 (0: 빈 칸, 1: 벽, 2: 바이러스)
  • 바이러스의 개수는 2 이상 10 이하, 빈 칸의 개수는 3 이상이다.

출력 📤

얻을 수 있는 안전 영역 크기의 최댓값을 출력한다.

첫 번째 시도: 완전 탐색과 BFS의 조합 🤯

Idea

N과 M의 크기가 최대 8x8로 매우 작다는 점에 주목했다. 이는 벽을 세울 수 있는 모든 경우의 수를 탐색해도 괜찮다는 신호다.

  1. 벽 세우기: 빈 칸(0) 중에 3개를 선택하여 벽을 세우는 모든 조합을 구한다. (itertools.combinations 활용)
  2. 바이러스 확산: 각 조합마다, 세워진 벽을 기준으로 바이러스가 얼마나 퍼지는지 BFS를 통해 계산한다.
  3. 안전 영역 계산: (전체 빈 칸 수 - 3 - 새로 감염된 칸 수)로 안전 영역을 구하고, 최댓값을 갱신한다.

모든 조합을 탐색해야 하므로, BFS를 호출할 때마다 visited 배열을 초기화하고 바이러스의 위치에서부터 다시 탐색을 시작하는 방식으로 접근했다.

Code

import sys
from collections import deque
from itertools import combinations

N, M = map(int, sys.stdin.readline().split())

board = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]
d_pos = [(0, 1), (1, 0), (-1, 0), (0, -1)]  # 우 하 상 좌
viruses = []

def bfs(x, y, new_walls, visited):
    global board
    global d_pos

    q = deque()
    q.append((x, y))

    visited[x][y] = True
    cnt = 0
    while q:
        r, c = q.popleft()

        for dr, dc in d_pos:
            nr = r + dr
            nc = c + dc

            if 0 <= nr < N and 0 <= nc < M and not visited[nr][nc]:
                if board[nr][nc] == 0 and (nr, nc) not in new_walls:
                    q.append((nr, nc))
                    visited[nr][nc] = True
                    cnt += 1

    return cnt

zero_li = []
virus_li = []
for i in range(N):
    for j in range(M):
        if board[i][j] == 0:
            zero_li.append((i,j))
        elif board[i][j] == 2:
            virus_li.append((i,j))

answer_virus = float('inf')
for walls in combinations(zero_li,3):
    virus_cnt = 0
    visited = [[False for _ in range(M)] for _ in range(N)]
    for vi in virus_li:
        vi_r, vi_c = vi
        cnt = bfs(vi_r, vi_c, walls, visited)
        virus_cnt += cnt
    del visited
    
    answer_virus = min(answer_virus, virus_cnt)

print(len(zero_li) - answer_virus - 3)

Result

  • 결과: 시간 초과 😭
  • BFS 탐색 중 (nr, nc) not in new_walls 부분에서 시간 복잡도 문제가 발생한 것으로 보인다. new_walls는 리스트이므로 in 연산은 매번 O(3)의 시간을 소모한다. BFS의 모든 정점 탐색마다 이 연산이 반복되면서 전체적인 시간 초과를 유발했다.

두 번째 시도: Set을 이용한 최적화 ✨

Idea

첫 시도의 시간 초과 원인이었던 in 연산을 최적화하기로 했다. 리스트 대신 해시셋(HashSet) 을 사용하면 in 연산의 시간 복잡도를 평균 O(1)로 줄일 수 있다.

  1. 벽을 세울 조합(tuple)을 set으로 변환한다.
  2. BFS 함수 내에서 벽을 확인할 때 (nr, nc) not in wall_set으로 변경한다.
  3. 추가로, BFS 함수를 약간 수정하여 모든 바이러스 위치를 초기에 큐에 넣고 한 번에 탐색을 시작하도록 구조를 개선했다. 이렇게 하면 BFS 호출 자체를 한 번으로 줄일 수 있다.

Code

import sys
from collections import deque
from itertools import combinations

input = sys.stdin.readline
N, M = map(int, input().split())
board = [list(map(int, input().split())) for _ in range(N)]
d_pos = [(0,1),(1,0),(-1,0),(0,-1)]

zero_li, virus_li = [], []
for i in range(N):
    for j in range(M):
        if board[i][j] == 0:
            zero_li.append((i,j))
        elif board[i][j] == 2:
            virus_li.append((i,j))

def bfs(wall_set):
    q = deque(virus_li)
    visited = [[False]*M for _ in range(N)]
    for r,c in virus_li:
        visited[r][c] = True

    virus_cnt = 0
    while q:
        r, c = q.popleft()
        for dr, dc in d_pos:
            nr, nc = r+dr, c+dc
            if 0 <= nr < N and 0 <= nc < M:
                if not visited[nr][nc] and board[nr][nc] == 0 and (nr,nc) not in wall_set:
                    visited[nr][nc] = True
                    q.append((nr,nc))
                    virus_cnt += 1
    return virus_cnt

answer = 0
for walls in combinations(zero_li, 3):
    wall_set = set(walls)
    virus_cnt = bfs(wall_set)
    safe_area = len(zero_li) - 3 - virus_cnt
    answer = max(answer, safe_area)

print(answer)

Result

  • 결과: 성공! 🎉
  • list를 set으로 바꾸는 간단한 최적화만으로 시간 초과 문제를 해결할 수 있었다. 작은 차이가 알고리즘의 성능에 큰 영향을 미친다는 것을 다시 한번 확인했다.

배운 점 및 개선할 부분 🤔

  • 자료구조의 중요성: 탐색 과정에서 특정 요소의 포함 여부를 자주 확인해야 할 때는 리스트(list)보다 해시셋(set)이 훨씬 효율적이다. 시간 복잡도 O(N)과 O(1)의 차이를 몸소 체험했다.
  • 브루트포스와 BFS의 결합: 문제의 제약 조건(N, M ≤ 8)을 보고 완전 탐색이 가능하다는 판단을 빠르게 내리는 것이 중요하다. 완전 탐색으로 모든 경우의 수를 만들고, 각 경우의 결과는 BFS와 같은 효율적인 탐색 알고리즘으로 검증하는 패턴에 익숙해져야겠다.
  • 코드 구조 개선: 첫 번째 코드에서는 각 바이러스마다 BFS를 따로 호출했지만, 두 번째 코드에서는 모든 바이러스를 큐에 미리 넣어두고 BFS를 한 번만 실행했다. 이처럼 불필요한 반복을 줄이는 방향으로 코드 구조를 개선하는 습관을 들여야겠다.

제약 조건이 작다면, 완전 탐색을 두려워하지 말자. 단, 탐색 과정의 각 단계는 최대한 효율적으로 구현해야 한다.

⁂