[백준] 14502 연구소 파이썬

링크 : www.acmicpc.net/problem/14502

 

푸는 방법

해당 문제가 왜 브루트포스에 있는가부터 고민을 하다가 해결하게 되었습니다.

 

벽을 3개 설치한다는 것은 0으로 되어있는 빈 공간 중 3개를 설치하는 것을 의미하고,

 

0인 행렬 포지션들을 나열해서 그중 3개를 선택하는 순열을 이용했습니다

 

그 다음, 백트래킹을 이용해 바이러스가 퍼지는 알고리즘을 설계하여 퍼뜨린 후

 

그 내부 안에서 0의 숫자를 세서 순열 중에서 최고값을 반환하게 만들었습니다.

 

나름 가독성 있게 써봤는데, 만족하셨으면 좋겠네요 감사합니다

코드

import itertools
import copy
N, M = map(int, (input().split()))
arr = [0 for x in range(N)]
for i in range(N):
    arr[i] = list(map(int, input().split()))

def count_space(temp):
    count = 0
    for i in range(N):
        for j in range(M):
            if temp[i][j]==0:
                count+=1
    return count

def spread_virus(x, y, temp):
    if y+1 < M:
        if temp[x][y + 1] == 0:
            temp[x][y + 1] = 2
            spread_virus(x, y + 1, temp)
    if x+1 < N:
        if temp[x + 1][y] == 0:
            temp[x + 1][y] = 2
            spread_virus(x + 1, y, temp)
    if y-1 >= 0:
        if temp[x][y - 1] == 0:
            temp[x][y - 1] = 2
            spread_virus(x, y-1, temp)
    if x-1 >= 0:
        if temp[x-1][y] == 0:
            temp[x-1][y] = 2
            spread_virus(x-1, y, temp)
    return temp

def find_virus():
    virus = list()
    for i in range(N):
        for j in range(M):
            if arr[i][j]==2:
                virus.append((i, j))
    return virus

W = list()
for i in range(N):
    for j in range(M):
        if arr[i][j]==0:
            W.append((i, j))

W = list(itertools.permutations(W, 3))
max_count = 0
for i, way in enumerate(W):
    temp = copy.deepcopy(arr)

    #make wall
    for x,y in way:
        temp[x][y] = 1

    #spread virus
    for x,y in find_virus():
        temp = spread_virus(x,y, temp)
    max_count = max(max_count, count_space(temp))

print(max_count)