Python으로 푸는 백준 14502. 연구소

백준 14502. 연구소

바이러스 유출을 막기 위해 연구소에 벽을 세우려고 할때, 

3개의 벽을 세워서 가장 많은 안전구역을 확보할 수 있는 경우

그 최대값을 반환하는 코드를 짜야한다.

백준 문제 보러가기

백준에서 푼 문제 리스트 보러가기

github에서 코드 보기

문제 조건

예제 3번 케이스에서 벽을 세우는 경우는 다음과 같다. 

8 8

2 2 2 2 2 2 2 2

2 2 2 2 2 2 2 2

2 2 2 2 2 2 2 2

2 2 2 2 2 2 2 2

2 2 2 2 2 2 2 2

1 2 2 2 2 2 2 2

0 1 2 2 2 2 2 2

0 0 1 2 2 2 2 2

문제 풀이

문제는 모든 경우의 수를 탐색해야 한다. 안전구역에 벽을 어디에 세울지를 짜야만 문제를 풀 수 있다. 

이 문제는 조합으로도 풀 수 있는 문제이므로, itertools를 활용해서 조합을 구하여 문제를 해결하려고 하였으나 시간 초과가 발생했다. 

그래서 재귀로 코드를 수정하여 제출하여 문제를 해결하였다. 

벽을 세울 수 있는 모든 경우의 수에 대하여 다음의 작업을 반복하고 가장 많이 확보할 수 있는 안전구역의 수를 반환하면 된다.

1. 안전구역에 벽 3개를 세운다.

2. 바이러스를 퍼뜨린다.

3. 안전구역의 수를 센다.

파이썬 코드

import sys
import copy
 
input = sys.stdin.readline
 
def spreadVirus(_virusList, c_arr):
    dx = [-1, 1, 0, 0]
    dy = [0, 0, -1, 1]
    spread_virus_count = 0
    global safe_area
 
    while _virusList:
        x, y = _virusList.pop()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
 
            if 0 <= nx and 0 <= ny and nx < n and ny < m:
                if c_arr[nx][ny] == 0:
                    c_arr[nx][ny] = 2
                    spread_virus_count += 1
                    _virusList.add((nx, ny))
    # 3 : 세운 벽의 수
    # 안전한 공간의 수를 반환
    return safe_area - spread_virus_count - 3
 
 
def setWall(start, wallCount):
    global maxVal
    global n
    global m
 
    # 벽을 다 세운 경우
    if wallCount == 0:
        copy_arr = copy.deepcopy(arr)
        copy_virusList = copy.deepcopy(virusList)
        # 바이러스를 퍼뜨린다.
        sCount = spreadVirus(copy_virusList, copy_arr)
        maxVal = max(sCount, maxVal)
        return
 
    # n번째 원소부터 루프를 돌린다
    for i in range(start, n*m):
        x = i // m
        y = i % m
 
        if arr[x][y] == 0:
            arr[x][y] = 1 # 벽을 세운다
            setWall(i+1, wallCount - 1)
            arr[x][y] = 0 # 최근에 세운 벽을 초기화
 
 
if __name__ == "__main__":
    n, m = map(int, input().strip().split())
    posList = []
    virusList = set()
    arr = []
    maxVal = 0
    safe_area = 0
 
    for i in range(n):
        arr.append(list(map(int, input().strip().split())))
 
    for i in range(n):
        for j in range(m):
            v = arr[i][j]
            if v == 2:
                virusList.add((i,j))
            elif v == 0:
                safe_area += 1
    setWall(0, 3)
    print(maxVal)
 

#백준 14502. 연구소 #백준 14502 연구소 #백준 연구소 #연구소 백준 #백준 14502 #백준 연구소 #python 백준 연구소 #python 연구소 #연구소 python