[백준/파이썬]14502 연구소

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

14502번: 연구소

문제

 

백준 14502번 연구소

처음 문제를 봤을 때 감이 안 잡혔다.. 대충 어떻게 풀지 두 가지 방법을 생각해 냈는데, 

1. 벽이 들어갈 수 있는 모든 경우 마다 bfs탐색을 하기

2. 바이러스를 퍼지게 하고, 막을 수 있는 공간이 딱 3이 나올 때를 체크하기

 

처음에 두번째 방법으로 풀어야겠다고 생각을 했는데.. 생각해 보면 해볼수록 답이 없는 방법이라는 걸 깨우치고 질문 게시판으로 달려갔다.

 

질문 게시판을 보니 combination을 쓴 글을 봤고 방법은 1번이라는 걸 알아차렸다.

 

문제를 풀기 위해서

 

입력 받는 공간(연구소)을 맵이라고 하자.

 

맵에서 0의 위치를 모두 탐색하고 탐색된 위치의 조합을 구해준다.

 

요것처럼

for i in range(n) :
    for j in range(m) :
        if map_[i][j] == 0 :
            zero_idx.append([i, j])
        elif map_[i][j] == 2 :
            virus_idx.append([i, j])

cmb_zero_idx = list(cmb(zero_idx, 3))

 

2일 때는 바이러스 퍼지는 걸 구현해야 하니 바이러스 인덱스를 virus_idx리스트에 넣어 줬다.

 

cmb_zero_idx를 출력해 보면

 

..... ([5, 4], [6, 0], [6, 5]), ([5, 4], [6, 0], [6, 6]), ([5, 4], [6, 2], [6, 3]), ([5, 4], [6, 2], [6, 4]), ([5, 4], [6, 2], [6, 5]), ([5, 4], [6, 2], [6, 6]), ([5, 4], [6, 3], [6, 4]), ([5, 4], [6, 3], [6, 5]), ([5, 4], [6, 3], [6, 6]), ([5, 4], [6, 4], [6, 5]), ([5, 4], [6, 4], [6, 6]), ([5, 4], [6, 5], [6, 6]), ([5, 5], [5, 6], [6, 0]), ([5, 5], [5, 6], [6, 2]), ([5, 5], [5, 6], [6, 3]), ([5, 5], [5, 6], [6, 4]), ([5, 5], [5, 6], [6, 5]), ([5, 5], [5, 6], [6, 6]), ([5, 5], [6, 0], [6, 2]), ([5, 5], [6, 0], [6, 3]), ([5, 5], [6, 0], [6, 4]), ([5, 5], [6, 0], [6, 5]), ([5, 5], [6, 0], [6, 6]), ([5, 5], [6, 2], [6, 3]), ([5, 5], [6, 2], [6, 4]), ([5, 5], [6, 2], [6, 5]), ([5, 5], [6, 2], [6, 6]),......

 

이런 식으로 출력되는 것을 알 수 있다.

 

그리고 구한 모든 조합의 각 인덱스에 벽을 세우고 bfs탐색으로 돌려보면 된다.

 

정답

from itertools import combinations as cmb
from collections import deque
import sys
import copy

input = sys.stdin.readline

def bfs() :
    global max_num
    while p_virus_idx :
        now = p_virus_idx.popleft()
        now_c, now_r = now[0], now[1]

        for k in range(4) :
            next_c, next_r = now_c + dx[k], now_r + dy[k]
            if next_c < 0 or next_r < 0 or next_c >= n or next_r >= m :
                continue
            if p_map_[next_c][next_r] == 0 :
                p_map_[next_c][next_r] = 2
                p_virus_idx.append([next_c, next_r])
    count = 0
    for w in range(n) :
        for q in range(m) :
            if p_map_[w][q] == 0 :
                count += 1

    return count

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

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

for i in range(n) :
    for j in range(m) :
        if map_[i][j] == 0 :
            zero_idx.append([i, j])
        elif map_[i][j] == 2 :
            virus_idx.append([i, j])

cmb_zero_idx = list(cmb(zero_idx, 3))
max_num = 0
for i in range(len(cmb_zero_idx)) :
    p_map_ = copy.deepcopy(map_)
    p_virus_idx = deque(copy.deepcopy(virus_idx))
    for j in range(3) :
        c, r = cmb_zero_idx[i][j][0], cmb_zero_idx[i][j][1]
        p_map_[c][r] = 1
    zero_count = bfs()
    if max_num < zero_count :
        max_num = zero_count

print(max_num)