[백준/python] 14502 연구소

문제

 

소스코드

from collections import deque

from itertools import combinations

n,m=map(int,input().split())

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

arr = map[:]

ans = 0

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

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

def virus():

    q = deque()

    # 위에서부터 맵을 돌다가 2를 만나면 바이러스를 퍼뜨림

    for i in range(n):

        for j in range(m):

            if arr[i][j] == 2:

                q.append((i,j))

   

    while q:

        x,y=q.popleft()

       

        for i in range(4):

            nx = x+dx[i]

            ny= y + dy[i]

           

            if 0 <= nx < n and 0 <= ny < m and arr[nx][ny] == 0:

                arr[nx][ny]=2

                q.append((nx,ny))

               

    # 0 세기

    cnt=0

    for i in range(n):

        for j in range(m):

            if arr[i][j]==0:

                cnt +=1

   

    return max(ans,cnt)

   

 

for comb in combinations([(i, j) for i in range(n) for j in range(m) if map[i][j] == 0], 3):

    arr = [row[:] for row in map]  

    for i, j in comb:

        arr[i][j] = 1 

    ans = virus()                         

                                   

print(ans)  

풀이

우선 조합으로 세 벽을 정한다. 그 후 바이러스를 2에서부터 퍼뜨린다(bfs). 다시 전부 돌며 0을 세고, 이를 반복하여 가장 max일 때를 출력한다.

 

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

14502번: 연구소