[Algorithm] 백준 14502 연구소 python

백준 14502 연구소 원문

1. 문제가 뭐였지

설명하기 복잡하다면 복잡하고 간단하다면 간단하다.

요런 식이다. 0은 그냥 빈 공간, 2는 바이러스, 1은 벽. 바이러스는 상하좌우로 번져나갈 수 있는데, 벽을 뚫지는 못한다.

벽 3개를 칠 수가 있는데, 벽 3개를 쳤을 때 가장 안전한 공간이 많은 경우를 구해야 한다.

2. 어떻게 풀었지

다아아아아아앙연히 시간초과 날 줄 알았다. 메모리도 많이 쓰고 좀 코드가 지저분한 것 같아서. 근데 꾸역꾸역 통과되더라니 상관 없는건가.

처음에는 막 벽의 위치를 어떻게 효율적으로 정해야 했나 싶었다. 근데 뭐 노답. 근데 문제 아래에 분류를 보니까 브루트 포스가 있길래...시간도 2초인가 그러길래.. 아 완전탐색을 해봐야겠구나 싶었다...ㅎㅎㅎㅎ...

일단 빈공간들을 따로 저장을 받았다. 바이러스가 있는 인덱스 도 저장을 따로 받았다.

1. 3개를 넣는다는 건 빈 공간 3개 골르면 되는거 아니야?! 바로 combination으로 뽑을 수 있는 공간 3개의 조합을 죄다 뽑아냈다.

2. 그리고 각각의 경우마다 bfs를 돌면서 탐색을 했다. 각각의 경우를 돌 때마다 나오는 안전 공간이 있을 것이고, 그거를 계속 비교해주었다.

3. bfs를 돌 때는, 각각의 바이러스 지점부터 돌았다.

3. 어디서 해맸지

완전탐색이 너무 오래걸릴 것 같았는데 내 머리로는 다른 방법이 생각이 안나서 그냥 그렇게 했다. 무조건 시간초과 걸릴 줄 알았는데.

python의 combination이나 deepcopy같은 친구들 덕분에 조금 더 수월하지 않았나 싶다.

완전탐색으로 가닥을 잡으니까 크게 어려운 부분은 없었다.

4. Code

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

input = sys.stdin.readline

#바이러스가 움직일 방향
dx = [-1,0,1,0]
dy = [0,1,0,-1]


def bfs(coboard,n,m,virus_place) :

    c = 0
    visited = [[False for _ in range(m)] for k in range(n)]
    q = deque()
    
    """
    사실 이 부분이 잘 짜인건지는 모르겠다. 더 좋은 방법이 있지 않을까?
    """
    
    #각각의 바이러스 포인트부터 시작
    for vp in virus_place :

        
        q.append(vp)
        visited[vp[0]][vp[1]] = True

        while q :
            front = q.popleft()

            for i in range(4) :
                newx = front[0] + dx[i]
                newy = front[1] + dy[i]

                if not (0 <= newx < n and 0<=newy<m) :
                    continue

                if visited[newx][newy] :
                    continue
                    
                if coboard[newx][newy] == 1 :
                    continue

                if coboard[newx][newy] == 0 :
                    coboard[newx][newy] = 2
                    visited[newx][newy] = True
                    q.append((newx,newy))
    
    #안전공간 카운트
    for i in range(n) :
        for j in range(m) :
            if coboard[i][j] == 0 :
                c += 1
                
    return c

def solve(n,m,board) :
	
    #최대값을 위한 세팅
    count = float("-inf")
    
    #안전한 지역, 바이러스가 있는 지역의 인덱스를 저장
    zero_place = []
    virus_place = []

    for i in range(n) :
        for j in range(m) :
            if board[i][j] == 0 :
                zero_place.append((i,j))
            elif board[i][j] == 2 :
                 virus_place.append((i,j))   
	
    #안전한 지역에다가 벽 3개를 세워야 하기 때문에, 안전한 지역 3개의 조합을 싹다 뽑음
    zero_combi = list(combinations(zero_place,3))
	
    #각각의 조합마다 탐색
    for combi in zero_combi :
		
        #board를 건드리면 안되니까 deepcopy
        coboard = deepcopy(board) 

        first = combi[0]
        sec = combi[1]
        third = combi[2]
	
        #뽑은 세개의 빈 공간을 벽으로 채우고
        coboard[first[0]][first[1]] , coboard[sec[0]][sec[1]], coboard[third[0]][third[1]] = 1,1,1
		
        #bfs를 돌리면 이 때 안전공간의 최대값을 리턴
        safe_count = bfs(coboard,n,m,virus_place)

        count = max(safe_count, count)

    print(count)

if __name__ == "__main__" :
    n,m = map(int,input().split())
    board = [list(map(int,input().split())) for _ in range(n)]

    solve(n,m,board)