백준 14502 연구소 1

이 문제는 완전탐색과 BFS를 이용해 해결 할 수 있는 대표적인 문제 유형 중 하나이다.

첫줄에는 n,m으로 각각 세로와 가로 길이가 입력이 들어오고
그 다음 n줄 동안 연구소의 구조를 입력 받는다.

예제 입력 중 하나는 아래와 같다 .

4 6
0 0 0 0 0 0
1 0 0 0 0 2
1 1 1 0 0 2
0 0 0 0 0 2

여기서 0은 빈공간, 1은 벽 그리고 2는 바이러스로 표현 할 수 있다.

문제에서는 우린 총 3개의 벽을 세울 수 있고 0으로 표시된 공간 중 3곳을 선택해 벽을 세우면 되는 것이다 .

그러면 여기서 첫번째로 0이 표시된곳 중 3개를 고르면 되기에 고등학교 수학에서 배운 조합을 활용하면 도움이 될 것이라 생각이 든다 .

모두 벽을 세운 이후에는 바이러스가 상하좌우 방향으로 퍼져나가는 것을 구현하고

바이러스가 전파 될 수 있는 공간에 모두 전파 된 이후 감염이 되지 않은 즉 숫자가 0인 구역이 가장 많을때 0이 총 몇개 있는지 알아내는 것이 이 문제가 요구 하는 조건이다.

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



n,m=map(int,sys.stdin.readline().split())
graph=[]
for i in range(n):
    a=list(map(int,sys.stdin.readline().split()))
    graph.append(a)

BFS 제에서 상하좌우로 움직이는 형식이 나온다면 제일 위에 줄의 dx ,dy 배열을 선언하고 푸는 것이 가장 짧은 코드로 문제에 접근 할 수 있는 기본적인 테크닉이라 이렇게 선언하고 가는 것이 좋다.

이 코드를 이용해 n,m과 그리고 연구소의 구조를 입력 받는다.

def count_safe(g):
    count=0
    for i in range(n):
        for j in range(m):
            if g[i][j]==0:
                count+=1
    return count

이 함수를 통해 안전구역 즉 숫자가 0인 부분을 연구소의 구조도에서 몇 개인지 구한다.

def select_wall(g):
    wall=[]
    for i in range(n):
        for j in range(m):
            if g[i][j]==0:
                wall.append((i,j))
    return list(combinations(wall,3))

이 함수는 연구소 구조도에서 안전구역의 좌표를 모두 구한후 그 중에서 3개를 고르는 조합들의 리스트를 리턴 해주는 함수 이다.

def bfs(g,remain):
    q=deque()
    visit=[[False for i in range(m)] for j in range(n)]


    for i in range(n):
        for j in range(m):
            if g[i][j]==2:
                q.append((i,j))

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

        if 0>x or y<0 or x>=n or y>=m:
            continue
        if visit[x][y] is True:
            continue


        

        visit[x][y] = True

        if g[x][y] == 1:
            continue

        if g[x][y]==0:
            g[x][y]=2
            remain=remain -1
        
        if g[x][y] == 2:
            for i in range(4):
                mx=x+dx[i]
                my=y+dy[i]
                q.append((mx,my))

    return remain

이제 이 bfs함수는 연구소의 구조와 안전구역의 개수를 입력으로 받고
바이러스가 모두 퍼진 이후의 안전구역의 개수를 리턴 해준다.

walls = select_wall(graph)
max_safe=-1
for i in walls:
    graph_c =copy.deepcopy(graph)

    graph_c[i[0][0]][i[0][1]]=1
    graph_c[i[1][0]][i[1][1]]=1
    graph_c[i[2][0]][i[2][1]]=1
   

    r=count_safe(graph_c)


    temp = bfs(graph_c,r)

    if temp>max_safe:
        max_safe=temp
   
print(max_safe)

이렇게 select_wall 함수를 이용해 벽을 놓은 3곳의 조합 리스트를 이용해
연구소에 벽을 설치한다

graph_c[i[0][0]][i[0][1]]=1
graph_c[i[1][0]][i[1][1]]=1
graph_c[i[2][0]][i[2][1]]=1

이렇게 벽을 3군데에 세우고

count_safe 함수를 이용해 안전 구역의 개수를 구한 후

bfs함수를 이용해 바이러스 전파 이후 안전 구역 개수를

벽을 놓는 조합의 개수만큼 반복하면서 안전 구역의 개수가 가장 많을 때를

구하면 되는 문제이다.

전체 소스 코드:

from itertools import combinations
from collections import deque
from pprint import pprint
import copy
import sys

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



n,m=map(int,sys.stdin.readline().split())
graph=[]
for i in range(n):
    a=list(map(int,sys.stdin.readline().split()))
    graph.append(a)

def count_safe(g):
    count=0
    for i in range(n):
        for j in range(m):
            if g[i][j]==0:
                count+=1
    return count

def select_wall(g):
    wall=[]
    for i in range(n):
        for j in range(m):
            if g[i][j]==0:
                wall.append((i,j))
    return list(combinations(wall,3))


def bfs(g,remain):
    q=deque()
    visit=[[False for i in range(m)] for j in range(n)]


    for i in range(n):
        for j in range(m):
            if g[i][j]==2:
                q.append((i,j))

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

        if 0>x or y<0 or x>=n or y>=m:
            continue
        if visit[x][y] is True:
            continue


        

        visit[x][y] = True

        if g[x][y] == 1:
            continue

        if g[x][y]==0:
            g[x][y]=2
            remain=remain -1
        
        if g[x][y] == 2:
            for i in range(4):
                mx=x+dx[i]
                my=y+dy[i]
                q.append((mx,my))

    return remain


walls = select_wall(graph)
max_safe=-1
for i in walls:
    graph_c =copy.deepcopy(graph)

    graph_c[i[0][0]][i[0][1]]=1
    graph_c[i[1][0]][i[1][1]]=1
    graph_c[i[2][0]][i[2][1]]=1
   

    r=count_safe(graph_c)


    temp = bfs(graph_c,r)

    if temp>max_safe:
        max_safe=temp
    


    

print(max_safe)