[BOJ] 14502번: 연구소 (Python)

 📖  문제

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

14502번: 연구소

 

💻  코드

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


def spread(b, q, case, N, M):
    # 깊은 복사
    b, q = copy.deepcopy(b), copy.deepcopy(q)
    # 벽으로 채우기
    for y, x in case:
        b[y][x] = 1
    # 4가지 방향 변수 선언
    dy, dx = (0, 0, 1, -1), (1, -1, 0, 0)
    # BFS
    while q:
        y, x = q.popleft()
        # 4가지 방향에 대해 빈 칸이면 바이러스 전파
        for d in range(4):
            ny, nx = y + dy[d], x + dx[d]
            if 0 <= ny < N and 0 <= nx < M and b[ny][nx] == 0:
                b[ny][nx] = 2
                q.append((ny, nx))
    # 빈칸의 개수 리턴
    return sum(row.count(0) for row in b)


def solution():
    # N, M 입력
    N, M = map(int, sys.stdin.readline().strip().split())
    # 전체 맵 입력
    b = list()
    for _ in range(N):
        b.append(list(map(int, sys.stdin.readline().strip().split())))
    # 바이러스 처음 위치 큐에 저장
    q = deque((y, x) for y in range(N) for x in range(M) if b[y][x] == 2)
    # 빈 칸 중 3개를 선택하는 모든 경우의 수
    cases = list(combinations([(y, x) for y in range(N) for x in range(M) if b[y][x] == 0], 3))
    # 모든 경우에 대해 바이러스 퍼트려보고 그 중 안전 지역 최댓값 출력
    print(max(spread(b, q, case, N, M) for case in cases))


solution()

 

🙌  한마디

파이썬에는 유용한 라이브러리가 참 많은 것 같다. 문법도 작성하기에 쉬운 편이다. 덕분에 코드를 직관적이며 짧게 작성할 수 있고, 가독성이 좋아 실수의 여지도 줄어든다. 이 문제를 풀면서 새삼 느낀 바이다. 풀이에는 브루트포스(완전 탐색) + BFS가 사용되었다. 빈 칸을 3개 선택하여 벽을 만드는 모든 경우에 대해서(완전탐색) 바이러스를 퍼뜨려보고(BFS) 안전 지역의 개수를 계산한다. 그 중에서 최댓값이 정답이된다.