백준 연구소 [14502] 파이썬(Python) 코드 + 해설

백준 14502 파이썬(python) 문제

#완전 탐색과 BFS 

이 문제는 바이러스가 유출된 연구소에서 벽을 세워 바이러스의 확산을 막고, 안전 영역의 최대 크기를 구하는 것이 목표이다.

문제 설명

• 연구소 지도: N x M 크기의 직사각형이며, 각 칸은 다음 중 하나이다:
  • 빈 칸: 0
  • 벽: 1
  • 바이러스: 2
• 바이러스 확산: 바이러스는 상하좌우로 인접한 빈 칸으로 퍼져나간다.
• 벽 세우기:
  • 새로 세울 수 있는 벽의 개수는 정확히 3개이다.
  • 벽은 빈 칸에만 세울 수 있다.
• 목표: 벽을 적절히 세워서 안전 영역(바이러스가 퍼질 수 없는 영역)의 크기를 최대로 만드는 것이다.

해결 방법: 완전 탐색과 BFS 사용

이 문제는 다음과 같은 방법으로 해결할 수 있다:

1. 모든 벽 세우기 경우의 수를 탐색한다:
   • 빈 칸 중에서 3개를 선택하여 벽을 세우는 모든 조합을 생성한다.
   • N과 M이 최대 8이므로 빈 칸의 최대 개수는 64개이다.
   • 따라서 빈 칸 64개 중 3개를 선택하는 조합은 약 41,664가지로 완전 탐색이 가능하다.
2. 각 경우마다 바이러스의 확산을 시뮬레이션한다:
   • 벽을 세운 후 바이러스가 어떻게 퍼지는지 BFS를 통해 시뮬레이션한다.
3. 안전 영역의 크기를 계산한다:
   • 바이러스가 퍼진 후 남은 빈 칸의 수를 계산하여 최대 값을 갱신한다.

구현 단계

1. 입력 받기:
   • 연구소의 크기 N, M과 연구소 지도를 입력받는다.
   • 빈 칸의 위치와 바이러스의 위치를 리스트에 저장한다.
2. 벽 세우기 조합 생성:
   • itertools.combinations를 사용하여 빈 칸 중 3개의 위치를 선택하는 모든 조합을 생성한다.
3. 각 조합에 대해 시뮬레이션 수행:
   • 선택한 위치에 벽을 세운다.
   • 바이러스의 확산을 BFS로 시뮬레이션한다.
   • 안전 영역의 크기를 계산하여 최대 값을 갱신한다.
   • 연구소 지도를 원래 상태로 복구한다.
4. 결과 출력:
   • 모든 경우를 탐색한 후 최대 안전 영역의 크기를 출력한다.

정답 코드

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

N, M = map(int, input().split())
lab = []
empty = []
virus = []

for i in range(N):
    row = list(map(int, input().split()))
    lab.append(row)
    for j in range(M):
        if row[j] == 0:
            empty.append((i, j))
        elif row[j] == 2:
            virus.append((i, j))

# 이동 방향: 상, 하, 좌, 우
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

max_safe_area = 0

for walls in combinations(empty, 3):
    # 연구소 복사
    temp_lab = copy.deepcopy(lab)
    # 벽 세우기
    for x, y in walls:
        temp_lab[x][y] = 1
    # 바이러스 확산 BFS
    queue = deque(virus)
    visited = [[False]*M for _ in range(N)]
    for x, y in virus:
        visited[x][y] = True
    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 < M:
                if temp_lab[nx][ny] == 0 and not visited[nx][ny]:
                    temp_lab[nx][ny] = 2
                    visited[nx][ny] = True
                    queue.append((nx, ny))
    # 안전 영역 계산
    safe_area = sum(row.count(0) for row in temp_lab)
    if safe_area > max_safe_area:
        max_safe_area = safe_area

print(max_safe_area)

코드 설명

• 입력 처리:
  • 연구소 지도를 입력받으면서 빈 칸과 바이러스의 위치를 저장한다.
• 벽 세우기 조합 생성:
  • itertools.combinations(empty, 3)를 사용하여 빈 칸 중 3개를 선택하는 모든 조합을 생성한다.
• 시뮬레이션:
  • 연구소 지도를 복사하여 temp_lab에 저장한다.
  • 선택한 위치에 벽을 세운다 (temp_lab[x][y] = 1).
  • 바이러스의 위치를 큐에 넣고 BFS를 수행하여 바이러스를 확산시킨다.
    • 확산 시 빈 칸(0)을 바이러스(2)로 바꾸고, 그 위치를 큐에 추가한다.
    • 이미 방문한 위치를 visited 배열로 관리하여 중복 방문을 방지한다.
• 안전 영역 계산:
  • 바이러스 확산이 끝난 후 남은 빈 칸의 수를 계산한다.
  • safe_area = sum(row.count(0) for row in temp_lab)
  • 최대 안전 영역 크기를 갱신한다.
• 결과 출력:
  • 모든 경우를 탐색한 후 max_safe_area를 출력한다.

14502 정답

도움이 되셨다면 공감과 댓글 부탁드립니다.