[백준 14502번] 연구소 파이썬 풀이

연구소

2 초

512 MB

93526

53829

30044

54.824%

문제

인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다.

연구소는 크기가 N×M인 직사각형으로 나타낼 수 있으며, 직사각형은 1×1 크기의 정사각형으로 나누어져 있다. 연구소는 빈 칸, 벽으로 이루어져 있으며, 벽은 칸 하나를 가득 차지한다. 

일부 칸은 바이러스가 존재하며, 이 바이러스는 상하좌우로 인접한 빈 칸으로 모두 퍼져나갈 수 있다. 새로 세울 수 있는 벽의 개수는 3개이며, 꼭 3개를 세워야 한다.

예를 들어, 아래와 같이 연구소가 생긴 경우를 살펴보자.

2 0 0 0 1 1 0
0 0 1 0 1 2 0
0 1 1 0 1 0 0
0 1 0 0 0 0 0
0 0 0 0 0 1 1
0 1 0 0 0 0 0
0 1 0 0 0 0 0

이때, 0은 빈 칸, 1은 벽, 2는 바이러스가 있는 곳이다. 아무런 벽을 세우지 않는다면, 바이러스는 모든 빈 칸으로 퍼져나갈 수 있다.

2행 1열, 1행 2열, 4행 6열에 벽을 세운다면 지도의 모양은 아래와 같아지게 된다.

2 1 0 0 1 1 0
1 0 1 0 1 2 0
0 1 1 0 1 0 0
0 1 0 0 0 1 0
0 0 0 0 0 1 1
0 1 0 0 0 0 0
0 1 0 0 0 0 0

바이러스가 퍼진 뒤의 모습은 아래와 같아진다.

2 1 0 0 1 1 2
1 0 1 0 1 2 2
0 1 1 0 1 2 2
0 1 0 0 0 1 2
0 0 0 0 0 1 1
0 1 0 0 0 0 0
0 1 0 0 0 0 0

 

벽을 3개 세운 뒤, 바이러스가 퍼질 수 없는 곳을 안전 영역이라고 한다. 위의 지도에서 안전 영역의 크기는 27이다.

연구소의 지도가 주어졌을 때 얻을 수 있는 안전 영역 크기의 최댓값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어진다. (3 ≤ N, M ≤ 8)

둘째 줄부터 N개의 줄에 지도의 모양이 주어진다. 0은 빈 칸, 1은 벽, 2는 바이러스가 있는 위치이다. 2의 개수는 2보다 크거나 같고, 10보다 작거나 같은 자연수이다.

빈 칸의 개수는 3개 이상이다.

출력

첫째 줄에 얻을 수 있는 안전 영역의 최대 크기를 출력한다.

예제 입력 1

7 7
2 0 0 0 1 1 0
0 0 1 0 1 2 0
0 1 1 0 1 0 0
0 1 0 0 0 0 0
0 0 0 0 0 1 1
0 1 0 0 0 0 0
0 1 0 0 0 0 0

예제 출력 1

27

예제 입력 2

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

예제 출력 2

9

예제 입력 3

8 8
2 0 0 0 0 0 0 2
2 0 0 0 0 0 0 2
2 0 0 0 0 0 0 2
2 0 0 0 0 0 0 2
2 0 0 0 0 0 0 2
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0

예제 출력 3

3

 

풀면서 아주 재밌었던 문제이다. 개인적으로 아주 잘 만든 문제라고 생각한다.

이 문제는 여러가지 개념들을 이용해야 해결이 가능한데(더 간단하게 푸는 방법이 있을수도 있음), 내가 이용한 개념은 다음과 같다.

 

1. BFS

2. 브루트포스

3. 깊은 복사

 

BFS는 바이러스(2)를 빈공간(0)으로 퍼뜨리기 위해 사용한다.

BFS의 시작좌표에서 상,하,좌,우의 네 방향을 조사하여 빈공간을 만난다면 해당 좌표로 이동하여 같은 과정을 반복함으로써, 바이러스를 배열에 퍼뜨릴수 있다.

 

브루트포스란 직역하면 '난폭한 힘'으로 쉽게말해 수 대입 노가다이다. 모든 경우의 수에 대해 알고리즘을 수행하는것으로 예를 들어 3자리 암호로 이루어진 잠금장치를 푼다고 가정할때, 000부터 999까지 모든 수를 대입해보는것이 이에 해당된다.

이 문제의 경우 벽을 세울 위치를 정하는것에 브루트포스 알고리즘을 적용시켜 임의의 3곳을 골라 벽을 세우고 이를 통해 만들어진 배열을 대상으로 BFS를 수행하여 바이러스를 퍼뜨린다.

위 과정에서 원본 배열이 손상될경우 임의의 3곳을 벽으로 설정하는과정이 어려워지므로 배열을 '깊은복사'하여 원본배열을 저장해두어야 하는 것이다.

 

깊은복사가 무엇인지 모른다면 공식 문서를 참고하길 바란다.

 

https://wikidocs.net/16038

12. 얕은 복사(shallow copy)와 깊은 복사(deep copy)

 

 

객체를 복사할때 깊은복사를 하지 않으면, 객체의 래퍼랜스(참조)만 복사하여(얕은 복사라고 한다) 한 객체를 두가지 이름으로 부를수 있게 되는것이지만 완전히 독립적인 새로운 객체를 만들고자 한다면 깊은복사를 하여 새로운 이름의 객체를 생성하고 그 객체에 원본 객체의 모든 내용물을 복사해주는 과정이 필요하다.

파이썬에서는 깊은 복사를 copy 라이브러리를 통해 제공하며 b = copy.deepcopy(a) 를 통해 객체a의 값을 b로 깊은 복사할 수 있다.

 

위의 3가지 개념을 종합하여 문제를 해결할 수 있는데, 내 풀이의 아이디어는 다음과 같다.

1. 브루트포스 알고리즘을 수행하여 빈공간중 3곳을 임의로 골라 벽을 세운다.(이때 깊은복사를 통해 원본 배열을 저장해둔다.)
2. 새롭게 생성된 배열을 바탕으로(벽이 세워진) BFS를 진행하여 바이러스를 퍼뜨린다.
3. 바이러스가 퍼진 배열을 검사하여 빈공간의 수를 카운트하고 이전결과보다 빈공간의 수가 늘어났다면 업데이트한다.

 

1번 과정이 사실상 문제의 핵심이라고 생각되는데, 2차원 배열을 반복하며 벽을 세우는것으로, 세워진 벽을 기억한채로 나머지 두 벽을 세워야 하기 때문에 재귀호출을 통하여 세워진 벽을 기억한채로 나머지 벽들을 세우고, 벽의 개수가 3개가 되면 2번,3번 과정을 수행한다. 위 과정을 반복하여 모든 경우에 대해 안전지대의 크기를 계산하고 함수가 종료되면 결과를 출력한다.

 

위 세과정을 코드로 옮기면 다음과 같다.

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

'''
연구소에 벽을 세워 안전영역의 최댓값을 구하라
벽을 3개 세운 뒤, 바이러스가 퍼질 수 없는 곳을 안전 영역이라고 한다.
벽은 꼭 3개를 세워야한다.
0은 빈 칸, 1은 벽, 2는 바이러스가 있는 곳이다. 아무런 벽을 세우지 않는다면, 바이러스는 모든 빈 칸으로 퍼져나갈 수 있다.

첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어진다. (3 ≤ N, M ≤ 8)

둘째 줄부터 N개의 줄에 지도의 모양이 주어진다. 0은 빈 칸, 1은 벽, 2는 바이러스가 있는 위치이다. 2의 개수는 2보다 크거나 같고, 10보다 작거나 같은 자연수이다.

빈 칸의 개수는 3개 이상이다.
'''
'''
아이디어 : 바이러스가 퍼져나가는것은 BFS를 통해 구현(고정), 벽을 세우는것은 빈공간중 3개를 골라 바이러스가 퍼져나가는 상황을 반복하여 확인한다.
3개의 벽이 세워지는 모든 경우의 수에 대하여 안전영역을 계산하고 안전영역의 최대값을 갱신하여 최종 출력한다.
'''
import sys
import copy # 깊은 복사를 위해
from collections import deque # BFS에 사용할 덱
input = sys.stdin.readline


# 세로의 크기(n:행), 가로의 크기(m:열)
n, m = map(int, input().split())
# 연구실 정보 입력받기
laboratory = [list(map(int, input().split())) for _ in range(n)]

result = 0  # 안전영역을 저장할 배열 => 재귀호출을 통해 업데이트한다.


# 네방향으로 이동하기 위한 방향 벡터
dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]


# 바이러스를 퍼뜨리기 위해 BFS => 2를 대상으로 상하좌우에 1이 없다면(즉 0이라면)주변으로 바이러스를 감염시킨다.
def bfs(copy_lab, x, y):
    queue = deque()  # BFS에 활용할 덱 생성
    queue.append([x, y])
    # 큐가 존재하는 동안 bfs
    while queue:
        a, b = queue.popleft()
        # 네방향으로 이동
        for i in range(4):
            mx = a + dx[i]
            my = b + dy[i]
            # 이동한 좌표가 배열의 범위를 벗어나지 않는지,해당좌표가 빈공간(0)인지 확인
            if 0 <= mx < n and 0 <= my < m and copy_lab[mx][my] == 0:
                copy_lab[mx][my] = 2  # 바이러스를 퍼뜨리고
                queue.append([mx, my])  # 해당 좌표 큐에 삽입


# 바이러스를 퍼뜨리기 위한 함수
# 벽이 설치된 깊은 복사된 배열을 탐색하여 2를 만나면 해당좌표를 기준으로 BFS를 수행한다.
def spread_virus(copy_lab):
    for i in range(n):
        for j in range(m):
            if copy_lab[i][j] == 2:
                bfs(copy_lab, i, j)


# 안전지대의 크기를 계산하여 리턴
def count_safety(copy_lab):
    safe = 0  # 안전지대의 영역
    for i in range(n):
        for j in range(m):
            if copy_lab[i][j] == 0:  # 안전영역을 만나면 safe 증가
                safe += 1
    return safe


# 배열을 탐색하며 0을 만나면 벽을 세우고, 벽의 개수가 3개가 되면 해당 배열을 바탕으로 BFS수행
# 1은 벽, 0은 빈공간 2는 바이러스
def make_wall(lab, wall):
    global result
    # 배열을 탐색하며 빈공간을 만나면 벽을 세우고, 벽의 개수가 3개가 넘어갔다면 BFS를 수행한다.
    for i in range(n):
        for j in range(m):
            if wall == 3:  # 벽을 3개 세우면 해당 배열을 바탕으로 바이러스 퍼뜨리기
                # 바이러스를 퍼뜨린후 안전지대를 계산하여 기존 안전지대보다 넓다면 갱신
                spread_virus(lab)
                # 안전지대의 최대값을 갱신하여 저장한다.
                result = max(result, count_safety(lab))
                return

            if lab[i][j] == 0:  # 빈공간을 만난다면 벽 세우기
                # 원본배열이 손상되지 않도록 배열을 복사
                # 연구실의 현재상태 저장 => 새롭게 새운 벽을 대상으로 BFS를 수행하기 위함
                copy_lab = copy.deepcopy(lab)
                # 벽을 세우고, 세운 벽의 좌표를 기억한채로 나머지 벽을 세워야 함 => 스택활용
                copy_lab[i][j] = 1
                # 재귀호출을 통해 벽의 좌표를 기억, 벽의 개수를 증가시켜 재귀호출
                make_wall(copy_lab, wall+1)


wall = 0
# 빈공간중 3곳이 될수 있는 모든 경우의 수에 대하여 벽을 세우고 탐색 진행
make_wall(laboratory, wall)
print(result)

 

visited배열을 이용한다거나, 재귀호출을 반복문으로 수정하면 시간복잡도를 좀 더 효율적으로 가다듬을수 있을것같아 다소 아쉽지만 더 실력이 늘으면 다시 시도해봐야겠다.

 

 

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

14502번: 연구소