[Python] 백준 14502 - 연구소

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

14502번: 연구소

 

처음에 문제 보고 어떻게 해야할지 막막했다.

바이러스를 막을 최적의 벽 3개를 어떻게 알아내지?????

 

근데 그런 걱정을 하는 문제가 아니었다.

입력 조건을 보면 그래프 크기 최대가 8*8 이다ㅋㅋㅋ

 

그냥 벽을 세울 수 있는 모든 경우의 수를 구하면 되는 문제.

 

나는 아래와 같이 풀었다. 

(안전 영역 = 그래프 크기 - 바이러스 개수 - 벽 개수)

BFS로 풀었고, 모든 경우의 수를 알기 위해서 itertools 라이브러리를 사용했다.

 

'''
0은 빈 칸
1은 벽
2는 바이러스 

벽을 3개 세운 뒤, 바이러스가 퍼질 수 없는 곳을 안전 영역이라고 한다. 
연구소의 지도가 주어졌을 때 얻을 수 있는 안전 영역 크기의 최댓값을 구하는 프로그램을 작성하시오.
'''

from collections import deque
from itertools import combinations

n,m = map(int,input().split())
lab = [list(map(int,input().split())) for _ in range(n)]

virus = deque() # 바이러스 위치 큐에 저장
empty = []  # 벽을 세울 수 있는 빈 칸 위치 저장

cnt_0 = 0
cnt_2 = 0

for i in range(n):
    for j in range(m):
        if lab[i][j] == 2:
            virus.append((i,j))
            cnt_2 +=1
        elif lab[i][j] == 0:
            empty.append((i,j))
            cnt_0 +=1

cnt_1 = n*m - cnt_0 - cnt_2

dxs = [1,-1,0,0]
dys = [0,0,1,-1]

minCnt = 64     # 바이러스 개수
# 벽 3개를 세울 수 있는 모든 경우의 수 탐색
walls = combinations(empty,3)
for wall1,wall2,wall3 in walls:
    lab[wall1[0]][wall1[1]] = 1
    lab[wall2[0]][wall2[1]] = 1
    lab[wall3[0]][wall3[1]] = 1
    cnt = cnt_2
    visited = [[0 for _ in range(m)] for _ in range(n)]
    
    q = virus.copy()
    while q:
        x,y = q.popleft()
        for dx,dy in zip(dxs,dys):
            nx, ny = x+dx, y+dy
            # 범위 내에 있고, 방문한적 없는 빈 칸이라면
            if 0<=nx<n and 0<=ny<m and not visited[nx][ny] and lab[nx][ny] == 0:
                visited[nx][ny] = 1
                q.append((nx,ny))
                cnt+=1

    minCnt = min(cnt,minCnt)

    # 벽 세운거 다시 폐기
    lab[wall1[0]][wall1[1]] = 0
    lab[wall2[0]][wall2[1]] = 0
    lab[wall3[0]][wall3[1]] = 0


print(n*m - minCnt - cnt_1-3)

재밌닿