[Python]백준 14502/연구소 / 조합 / 배열 복사 copy

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

14502번: 연구소

⚡️ 문제 설명

벽을 3개 세운 뒤, 바이러스가 퍼질 수 없는 곳을 안전 영역이라고 한다. 

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

⚡️ 해결 방법

ex)

1 단계 : 빈칸인 위치 모두 찾기

empty_list = []
for empty_x in range(n):
    for empty_y in range(m):
        if initGraph[empty_x][empty_y] == 0:
            empty_list.append([empty_x, empty_y])

empty_list :

[[0, 1], [0, 2], [0, 3], [0, 6], 
 [1, 0], [1, 1], [1, 3], [1, 6], 
 [2, 0], [2, 3], [2, 5], [2, 6], 
 [3, 0], [3, 2], [3, 3], [3, 4], [3, 5], [3, 6], 
 [4, 0], [4, 1], [4, 2], [4, 3], [4, 4], 
 [5, 0], [5, 2], [5, 3], [5, 4], [5, 5], [5, 6], 
 [6, 0], [6, 2], [6, 3], [6, 4], [6, 5], [6, 6]]

 

2단계 : 빈칸인 위치 중 3개 조합 만들기

from itertools import combinations

파이썬 내장 모듈 itertools를 이용한다

조합은 combinations 함수를 이용한다.

list(combinations(empty_list, 3))

 

 

3단계 : 3개의 조합마다 바이러스를 퍼뜨려서 가장 적은 바이러스 수 찾기 + bfs 이용

result = len(empty_list)
for three_wall in three_wall_list:
    virusGraph = copy.deepcopy(initGraph)
    # 벽 세개 만들기
    for wall in three_wall:
        wall_x, wall_y = wall
        virusGraph[wall_x][wall_y] = 1

    virusCount = 0
    for i in range(n):
        for j in range(m):
            if initGraph[i][j] == 2:
                virusCount += bfs(i, j, virusGraph)
    #바이러스가 가장 적게 퍼진 수를 저장하기
    if virusCount < result:
        result = virusCount

 

4단계 : 결과

= 처음의 0의 개수 - 가장적게 퍼진 바이러스의 수 - 세운 벽의 수 3

print(len(empty_list) - result - 3)

 

*주의할점*

2차원 배열을 복사할 때

*copy 모듈 이용

import copy
virusGraph = copy.deepcopy(initGraph)

*슬라이스 이용

virusGraph=[g[:] for g in initGraph]

 

나는 copy모듈을 이용하여 통과하였지만 슬라이스가 훨씬 속도가 빠르다

다음에 2차원 배열을 복사할 일이 있을 때는 슬라이스 모듈을 사용하자.

위에가 슬라이스를 이용하여 배열을 복사하였고, 아래가 copy 모듈을 사용하였다. 슬라이스를 이용하는 것이 빠르다는 것을 알 수 있다.

 

 

⚡️ 코드

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

input = sys.stdin.readline

n, m = map(int, input().split())

initGraph = [list(map(int, input().split())) for _ in range(n)]
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]


def bfs(x, y, virusGraph):
    virus = 0
    queue = deque()
    queue.append((x, y))
    while queue:
        x, y = queue.popleft()
        for k in range(4):
            nx = x + dx[k]
            ny = y + dy[k]
            if nx < 0 or ny < 0 or nx >= n or ny >= m:
                continue
            if virusGraph[nx][ny] == 1:
                continue
            #virus 퍼뜨리기
            if virusGraph[nx][ny] == 0:
                virusGraph[nx][ny] = 2
                virus += 1
                queue.append((nx, ny))
    return virus


# 빈칸인 위치 찾기
empty_list = []
for empty_x in range(n):
    for empty_y in range(m):
        if initGraph[empty_x][empty_y] == 0:
            empty_list.append([empty_x, empty_y])

# 빈칸 위치 중 3개 조합 만들기
three_wall_list = list(combinations(empty_list, 3))

# 빈칸의 조합마다 바이러스 파뜨려서 가장 적은 바이러스의 수 찾기
result = len(empty_list)
for three_wall in three_wall_list:
    virusGraph = copy.deepcopy(initGraph)
    # 벽 세개 만들기
    for wall in three_wall:
        wall_x, wall_y = wall
        virusGraph[wall_x][wall_y] = 1

    virusCount = 0
    for i in range(n):
        for j in range(m):
            if initGraph[i][j] == 2:
                virusCount += bfs(i, j, virusGraph)
    #바이러스가 가장 적게 퍼진수를 저장하기
    if virusCount < result:
        result = virusCount

print(len(empty_list) - result - 3)