[백준] #14502. 연구소 (python) - 파이썬 풀이 (BFS, 깊은 복사)

문제

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

14502번: 연구소

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

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

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

 

입력

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

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

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

 

출력

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

 

예시 입력

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

 

예시 출력

27

 

 

풀이

 

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

n, m = map(int, sys.stdin.readline().split())
graph = []

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

for _ in range(n):
    graph.append(list(map(int, sys.stdin.readline().split())))

def bfs(vx, vy):
    q = deque([])
    q.append([vx, vy])

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

        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]

            if (0 <= nx < n) and (0 <= ny < m) :
                if ((tmp_graph[nx][ny] == 0) or (tmp_graph[nx][ny] == 2)) and not visited[nx][ny]:
                    tmp_graph[nx][ny] = 2
                    visited[nx][ny] = 1
                    q.append([nx, ny])

def check_area(tmp_graph):
    area = 0        
    for j in range(n):
        for k in range(m):
            if tmp_graph[j][k] == 0:
                area += 1
    return area
    

visited = [[0] * m for _ in range(n)]
points = []
virus_points = []

# 0인 좌표, 2인 좌표들 찾기
for j in range(n):
    for k in range(m):
        if graph[j][k] == 0:
            points.append([j, k])
        elif graph[j][k] == 2:
            virus_points.append([j, k])

search_points = list(combinations(points, 3))
areas = []

for sp in search_points:
    tmp_graph = copy.deepcopy(graph)
    visited = [[0] * m for _ in range(n)]

    for p in sp:
        sx, sy = p
        tmp_graph[sx][sy] = 1
    for vp in virus_points:
        vx, vy = vp
        if not visited[vx][vy]:
            bfs(vx, vy) 
    area = check_area(tmp_graph)
    areas.append(area)

print(max(areas))

 

1. 가능한 벽 조합 만들기

우선, 벽을 3개 세워야 한다는 조건이 있어서 벽을 세울 수 있는 좌표들을 찾았다.

좌표들을 기반으로 파이썬의 itertools 모듈의 combinations 함수를 사용해 가능한 조합들을 만들었다.

 

+ 반복문 도는 김에 bfs 탐색을 위해 바이러스가 있는 좌표들도 미리 저장했다.

 

🔹반복문 동작 과정

- 원본 graph 정보를 깊은 복사한 tmp_graph를 생성한다.

- 해당하는 조합 좌표들을 가지고 벽을 세운다. (tmp_graph 값을 1로 변경)

- 바이러스 퍼뜨리기 => 아까 만든 바이러스가 있는 좌표들을 기반으로 bfs를 하며 바이러스를 퍼뜨린다.

- bfs가 끝난 결과를 기반으로 안전 구역을 확인한다.

 

2. BFS 호출

바이러스를 퍼뜨리기 위해 BFS를 호출한다. 상하좌우로 탐색하면서 tmp_graph의 값을 2로 바꾼다.

 

3. 안전 구역 확인

check_area 함수를 통해 안전 구역의 수를 확인한다. 그중 최댓값을 찾아 출력한다.

 

 

얕은 복사와 깊은 복사

 

이번에도 시행착오가 있다.

처음에는 graph 값을 복사한 tmp_graph를 생성할 때 슬라이싱을 했다. 예전에 값을 복사할 때 그렇게 했던 기억이 있다. 그런데 tmp_graph 값이 바뀔 때마다 자꾸 graph 값이 바뀌었다.

 

다음으로 리스트의 copy 명령어를 시도했는데 또 같은 오류가 생겼다. 찾아보니 파이썬에서 깊은 복사를 하려면 내장 모듈 copy의 deepcopy 메소드를 사용해야 했다. 일차원 리스트라면 깊은 복사와 얕은 복사의 결과가 같지만, 이차원 리스트는 안에 요소들이 있기 때문에 결과가 달라진다.

 

얕은 복사와 깊은 복사의 차이는 복합 객체에 대해서만 유효하다. 복합객체는 리스트나 클래스처럼 다른 객체들을 포함하는 객체를 말한다.

얕은 복사는 새로운 복합 객체를 생성하고 원본 객체가 포함하는 동일한 객체들을 삽입한다.

깊은 복사는 새로운 복합 객체를 생성하고 재귀적으로 원본 객체가 포함하는 객체들의 복사본을 삽입한다.