[Python] 삼성 sw 역량 테스트 기출 - 연구소

www.acmicpc.net/problem/14502

14502번: 연구소

[ 알고리즘 ]

BFS, 브루트포스

 

[문제 접근]

브루트포스 + BFS를 이용하여 해결하는 문제이다.

N과 M의 범위가 크지 않은 경우라 브루트포스 방법을 생각해내었다. 

벽은 3개만 추가로 설치할 수 있으므로 벽이 설치될 수 있는 경우의 수를 구하고, 이를 Counter 을 이용하여 안전지대의 개수를 counting 한 후 Max 값만 업데이트 해주면 된다.

 

[코드]

from collections import deque
from collections import Counter
from itertools import combinations
import copy

def BFS(graph):
    global N
    global M
    dx=[-1,1,0,0]
    dy=[0,0,-1,1]

    que=deque()

    for i in range(N):
        for j in range(M):
            if graph[i][j]==2:
                que.append((i,j))

    while que:
        x,y=que.popleft()

        for k in range(4):
            xx=dx[k]
            yy=dy[k]

            if x+xx<0 or y+yy<0 or x+xx>=N or y+yy>=M:
                continue

            if graph[x+xx][y+yy]==0:
                graph[x+xx][y+yy]=2
                que.append((x+xx,y+yy))

    return graph

N,M=map(int,input().split())
graph=[]
List=[]
Max=0

for _ in range(N):
    graph.append(list(map(int,input().split())))

for i in range(N):
    for j in range(M):
        if graph[i][j]==0:
            List.append((i,j))

combination=list(combinations(List,3)) # 3개 세울 수 있는 벽의 조합들
n=len(combination) # 조합 개수

for i in range(n):
    com=combination[i]

    x1,y1=com[0][0],com[0][1]
    x2,y2=com[1][0],com[1][1]
    x3,y3=com[2][0],com[2][1]

    Graph=copy.deepcopy(graph)

    Graph[x1][y1]=1 # 벽 세우기
    Graph[x2][y2]=1
    Graph[x3][y3]=1

    result=BFS(Graph)
    cnt=0
    for j in range(N):
        counter=Counter(result[j])
        cnt+=counter[0]

    if Max < cnt:
        Max=cnt


print(Max)