[백준] 14502 _연구소 (python 파이썬)

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

14502번: 연구소

풀이 과정 

 

풀이는 3파트로 나누어서 풀었다.

 

1) 벽세우기

2) 바이러스 감염

3) 안전 영역 구하기

 

상대적으로 생각하기 쉬운 2)바이러스 감염은 dfs나 bfs를 사용하고

1)벽세우기 파트는 입력값에 N과 M이 작은 것을 보고(최대 8) 브루트포스 방법을 사용하기로 결정.

 

먼저 지도에서 빈공간들의 좌표를 모아 저장한다.

그 후 파이썬의 combinations를 사용하여 벽의 세워지는 모든 경우의 수를 추출한다.

 

그후 Deepcopy를 사용해 2차원 리스트를 복사해오고 

빈공간 3곳에 벽을 세운다.

 

그리고 각 바이러스 위치에 대해 infection(dfs)함수를 실행

def infection(x, y):
    if x <= -1 or x >= N or y <= -1 or y >= M:
        return False

    if B[x][y] == 1:
        return False

    if B[x][y] == 0 or B[x][y] == 2:
        B[x][y] = 3 # 바이러스 감염 3
        infection(x - 1, y)
        infection(x + 1, y)
        infection(x, y - 1)
        infection(x, y + 1)
        return True
    return False

 

좌표의 경계값이 넘어가거나 벽이 있는 경우는 return False시켜주고 빈공간(0)이거나 바이러스(2)가 있는경우 

숫자 3을 사용하여 감염시켰다는것을 표현하였다. 이후 상하좌우 dfs방법으로 탐색

 

마지막으로 리스트B에 빈공간(0)의 개수를 세고 결과값을 모아주는 리스트(resultBox)에 추가.

resultBox에서 최대값을 결과로 출력하면 끝이다.

 

파이썬으로 작성한 전체 코드는 다음과 같다.

 

import sys
import copy
from itertools import combinations

input = sys.stdin.readline
sys.setrecursionlimit(10**6)

blank = [] # 빈공간 리스트
box = [] # 지도
virus = [] # 바이러스 위치 리스트
resultBox = []

# 입력
N, M = map(int, input().split())
for i in range(N):
    box.append([int(x) for x in input().split()])
    for j in range(M):
        if box[i][j] == 2:  # 바이러스 위치 저장
            virus.append([i,j])
        elif box[i][j] == 0:  # 빈공간, 벽이 들어 갈 수 있는 위치 저장
            blank.append([i,j])

def infection(x, y):
    if x <= -1 or x >= N or y <= -1 or y >= M:
        return False

    if B[x][y] == 1:
        return False

    if B[x][y] == 0 or B[x][y] == 2:
        B[x][y] = 3 # 바이러스 감염 3
        infection(x - 1, y)
        infection(x + 1, y)
        infection(x, y - 1)
        infection(x, y + 1)
        return True
    return False

for a in combinations(blank, 3):
    B = copy.deepcopy(box)
    for s in a:
        p = s[0]
        q = s[1]
        B[p][q] = 1  # 벽 세우기
    for v in virus:
        infection(v[0], v[1])

    result = 0
    for i in range(N):
        result += B[i].count(0)
    resultBox.append(result)

print(max(resultBox))