[13-02 DFS/BFS 문제] 연구소

최근 보고 있는 책인  '이것이 코딩테스트다 with 파이썬 편_나동빈_한빛미디어' 에 있는 문제이다.

www.hanbit.co.kr/store/books/look.php?p_code=B8945183661

이것이 취업을 위한 코딩 테스트다 with 파이썬

 

 

문제는 백준에 있다.

www.acmicpc.net/problem/14502

14502번: 연구소

 

 

import itertools
import copy

n,m = map(int,input().split())
current_lab = []
for i in range(n):
    current_lab.append(list(map(int,input().split())))

dx = [-1,0,1,0]
dy = [0,1,0,-1]

data = []

for i in range(n):
    for j in range(m):
        if current_lab[i][j] == 0:
            data.append([i,j])

iter_data = list(itertools.combinations(data,3))


def virus(x,y):
    for i in range(4):
        nx = x+dx[i]
        ny = y+dy[i]

        # 퍼질 수 있음
        if nx>-1 and ny>-1 and nx < n and ny < m :
            if after_lab[nx][ny] == 0:
                after_lab[nx][ny] = 2
                virus(nx,ny)



def count_safe(now):
    safe_count = 0
    for i in range(n):
        safe_count += now[i].count(0)

    return safe_count


result = 0
for new_wall in iter_data:
    after_lab = copy.deepcopy(current_lab)
    for new in new_wall :
        after_lab[new[0]][new[1]] = 1

    for i in range(n):
        for j in range(m):
            if after_lab[i][j] == 2:
                virus(i,j)

    result = max(result,count_safe(after_lab))


print(result)