백준 boj 파이썬 14502 연구소

벽의 위치를 3개 세우는 방식이 사람마다 다른 것 같다.

나는 from itertools import combinations을 이용하였다.

이차원 배열을 돌면서 벽의 위치를 수집하고

벽의 개수가 n개면 0~n-1까지의 리스트를 만들고

combinations(orders,3)로 3개의 조합을 뽑는 리스트를 생성 후

각각 벽을 세워줬다.

무언가 어려워보이지 않지만 실제로 풀다보면 굉장히 실수도 많이 발생하고

구현하기에 상당히 빡빡한 문제라는 생각이 들었다.

굉장히 탄탄한 벽 같다는 느낌을 받았다.

 

벽 위치 수집 -> combinations을 이용하여 각각 경우의 수마다 벽을 세우고->바이러스를 퍼트리고-> 모든 경우의 수 반복 후->안전영역 계산

 

import sys
from collections import deque
from itertools import combinations
 
#sys.setrecursionlimit(1000000)
 
 
 
## 콤비네이션 함수로 3개 뿌리고 그 3개마다 bfs 탐색해서 안전영역 최대의 크기를 구한다.
 
## 바이러스 퍼트리기
def virus():
    #print(q)
    while q:
       x,y= q.popleft()
 
       for k in range(4):
           nx=x+dx[k]
           ny=y+dy[k]
           if 0<=nx<n and 0<=ny<m:
               if temp[nx][ny]==0:
                   temp[nx][ny]=2
                   q.append((nx,ny))
    #for i in range(n):
    #        for j in range(m):
    #            print(temp[i][j],end=' ')
    #        print()
    #print()
        
                    
 
if __name__=='__main__':
    #sys.stdin=open("input.txt", "rt")
    
    n,m=map(int,input().split()) ##n=행,m=열
    board=[list(map(int,input().split())) for _ in range(n)]
    wall=[]
 
    ##벽의 후보 위치 수집
    for i in range(n):
        for j in range(m):
            if board[i][j]==0:
                wall.append((i,j))  ##[(0,1),(1,2),~~]
    w=len(wall) ##벽을 세울 수 있는 위치의 크기
    #print(w)
    order=[x for x in range(w)]
    
 
    wall_com=list(combinations(order,3)) ##벽의 후보 3개 뽑기 [(0,1,2),(2,3,4)~~~~]
  #  print(wall_com)
    q=deque()
    dx=[0,0,-1,1]
    dy=[1,-1,0,0]
 
 
    temp=[[0]*m for _ in range(n)]
 
    
    ans=-3 ##안전 영역 최대 크기
    ## 벽 세우기 (각각 케이스마다)
   # print((wall_com))
    for x in wall_com:
        #print(x)
        ch=[[-1]*m for _ in range(n)] 
        ##초기화 시키기 그래프
        for i in range(n):
            for j in range(m): 
                temp[i][j]=board[i][j]
        ##벽 세우기
        for y in x:
            a=(wall[y][0])
            b=(wall[y][1])
            temp[a][b]=1
           # print(a,b)
        #print()
         ## 바이러스 있는 위치 수집
        for i in range(n):
           for j in range(m):
           
          
             if temp[i][j]==2:
               
                q.append((i,j))
 
        virus() ##바이러스 퍼트리기
        ##안전 영역 계산
        cnt=0
        for i in range(n):
            for j in range(m):
               if temp[i][j]==0:
                   cnt+=1
        ans=max(ans,cnt)
     
        #if ans==14:
        #    for i in range(n):
        #       for j in range(m):
        #         print(temp[i][j],end=' ')
        #       print()
        #    exit()
    #    print(ans)
    print(ans)