[Python] 14502번 연구소

 

 

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

14502번: 연구소

---

 

24/01/06

 

 

BFS와 브루트포스 연습 문제로, 구현하는 중간에 조금 꼬여서 살짝 해멨던 문제이다.

---

 

문제 접근 방식:

 

 

문제 자체는 단순하다.

 

벽을 $3$개 세워야만 하고, 그렇게 벽을 세운 뒤에는 BFS를 돌리면 된다.

 

즉,  $64\times 64\times 64 \approx 260,000$번 정도의 BFS를 수행하면 된다.

 

BFS를 진행할 때에는 바이러스가 있는 부분을 큐에 넣고 BFS를 진행하면 된다.

 

BFS를 진행한 이후에는 안전 구역을 따로 카운팅 해주면 된다.

 

내가 처음으로 구현했던 방법은, 기존 배열을 함수의 인자로 넣어서 벽을 세우는 새로운 배열을 내보내는 함수를 구성하도록 구현하는 방법을 취했다.

 

즉, 벽 세우는 함수 따로, BFS를 진행하는 함수 따로 두었는데, 어째서인지 자꾸 원본 배열이 훼손되어서 잘못된 결과를 내보냈었다.

 

이후 방법을 바꿔서 BFS를 진행할 때 visited배열을 따로 만들어서 원본 배열을 훼손하지 않도록 만들어 주었다.

 

아이디어 자체는 그렇게 어려운 문제는 아니었으나, 구현의 디테일을 잘 잡아야 하는 문제이다.

 

나의 경우 itertools의 combinations함수를 활용하여 쉽게 구현했다.   

 

---

아래는 내가 위의 접근 방식과 같이 작성한 파이썬 코드이다. 더보기를 누르면 확인할 수 있다.

# 14502번 연구소
# BFS, 브루트 포스
'''
접근 방법:
벽을 총 3개 세울 수 있고, 칸 수는 최대 64개 이므로,
64*64*64=약 26만 번 정도의 BFS로 구현 할 수 있다.
'''
import sys
input = sys.stdin.readline
from collections import deque
from itertools import combinations

def BFS(lab, will_stand, N, M):
    dr, dc = [-1, 1, 0, 0], [0, 0, -1, 1]
    queue = deque()
    visited = [[0 for _ in range(M)] for _ in range(N)]
    for i in range(N):
        for j in range(M):
            if lab[i][j] == 2:
                queue.append((i, j))
                visited[i][j] = 1
            elif (i, j) in will_stand:
                visited[i][j] = 1
            elif lab[i][j] == 1:
                visited[i][j] = 1
    while queue:
        r, c = queue.popleft()
        for i in range(4):
            nr, nc = r+dr[i], c+dc[i]
            if 0 <= nr < N and 0 <= nc < M and visited[nr][nc] == 0:
                visited[nr][nc] = 1
                queue.append((nr, nc))
    safe_zone = 0
    for i in range(N):
        for j in range(M):
            if visited[i][j] == 0:
                safe_zone += 1
    return safe_zone

def main():
    N, M = map(int, input().rstrip().split())
    lab = [list(map(int, input().rstrip().split())) for _ in range(N)]
    pos_li = [(i, j) for i in range(N) for j in range(M) if lab[i][j] == 0]
    max_safe_zone = 0
    for will_stand in combinations(pos_li, 3):
        safe_zone = BFS(lab, will_stand, N, M)
        if safe_zone > max_safe_zone:
            max_safe_zone = safe_zone
    print(max_safe_zone)

main()