백준 14502 연구소 (python)

문제

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

깊은 복사와 얕은 복사

파이썬에서는 리스트를 크게 얕은 복사와 깊은 복사 2가지로 복사하고 있습니다.

얕은 복사

• 객체의 주소값을 복사하는 경우입니다.
• 대입 연산자 (‘=’) 를 사용해서 리스트를 다른 리스트에 대입하는 방식입니다.
• 변형(mutable) 객체는 복사한 객체의 내용을 변경하면 원본 리스트의 내용도 변합니다
• 불변형(immutable) 객체는 복사한 객체의 내용을 변경해도 원본에는 영향이 없습니다.

깊은 복사

• 객체의 데이터만을 복사하는 경우입니다.
• copy 모듈의 copy() ,deepcopy() 함수를 사용합니다.
• 1차원 리스트는 copy()를 사용하고 2차원 이상의 배열은 deepcopy() 함수를 사용합니다. virusGraph = copy.deepcopy(virus_BFS(j[0], j[1], tempGraph))
• list slicing 방식 [:] 입니다.
• list slicing이 copy 모듈을 사용하는 것보다 빠릅니다.
• 1차원 리스트 : tempNum = num[:]
• 2차원 리스트 :  tempGraph = [ i [:] for i in Graph]

나의 접근법

위 문제는 이것이 코딩테스트다 with 파이썬 에 수록된 문제입니다. 저는 접근하는 방법만 보고 문제를 풀어보았습니다. 위 문제는 지도의 최대 사이즈가 8x8로 칸막이 3개를 설치하는 방법은 최대 64C3 = 41664 입니다. 따라서 저는 그래프의 정보를 입력받을 때 ‘0’ 의 좌표를 zeroLocate 리스트에 저장시키고 itertools 패키지의 combinations 모듈을 활용해서 64C3의 경우의 수 마다 ‘0’의 위치에 벽을 세웠습니다. 그 후 바이러스의 위치를 BFS로 퍼뜨려 남은 ‘0’의 개수를 세는 방식으로 풀었습니다.

첫번째 제출 코드

다음은 제 첫번째 코드입니다.

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

N, M = map(int, sys.stdin.readline().split())

# 벽 세우고 virus가 퍼진 후 그래프
def virus_BFS(x, y, tempGraph):
    queue = deque()
    queue.append([x, y])
    tempGraph[x][y] = 2
    # 상 하 좌 우
    dx = [1, -1, 0, 0]
    dy = [0, 0, -1, 1]

    while queue:
        v = queue.popleft()

        for i in range(4):
            nx = v[0] + dx[i]
            ny = v[1] + dy[i]
            if nx >= 0 and nx < N and ny >= 0 and ny <M:
                if tempGraph[nx][ny] == 0:
                    tempGraph[nx][ny] = 2
                    queue.append([nx, ny])

    return tempGraph

graph = []
zeroLocate = [] #0의 좌표를 저장한 리스트
virusLocate = [] # 바이러스의 위치를 저장한 리스트
virusGraph = [] # 바이러스가 퍼진 그래프
tempGraph = [] # 그래프의 내용을 변경하기 위한 임시 그래프
combinationsZeroLocate = [] #0의 좌표 중 3개 뽑는 경우의 수를 저장한 리스트
result = 0 # 최종 안전 영역

for i in range(N):
    graph.append(list(map(int, sys.stdin.readline().split())))
    for j in range(M):
        if graph[i][j] == 0:
            zeroLocate.append([i, j])
        elif graph[i][j] == 2:
            virusLocate.append([i, j])

virusGraph = copy.deepcopy(graph)
combinationsZeroLocate = (list(combinations(zeroLocate, 3)))

for i in combinationsZeroLocate:
    temp = 0
    tempGraph = copy.deepcopy(graph)

    tempGraph[i[0][0]][i[0][1]] = 1
    tempGraph[i[1][0]][i[1][1]] = 1
    tempGraph[i[2][0]][i[2][1]] = 1

    for j in virusLocate:
        virusGraph = copy.deepcopy(virus_BFS(j[0], j[1], tempGraph))

    for j in virusGraph:
        temp += j.count(0)

    result = max(temp, result)

print(result)

 

인접행렬로 인한 시간복잡도 :O(8^2) 8x8 크기중에서 3개 뽑는 경우의 수: (8x8) C 3

64C3 * O(8*2) => 약 8^5 8^5 < 10^2 = 100,000 이라서 시간초과가 안 뜰줄 알고 이렇게 풀이했습니다. 하지만 백준에서 python3로 제출했을 경우 시간초과가 발생했습니다.
그런데 pypy3로 제출한 경우에는 맞았습니다.

제가 간과 했던 것이 저는 지도를 복사하기 위해 deepcopy라는 함수를 사용했는데 deepcopy의 시간복잡도는 계산하지 않았습니다.

deepcopy 부분을 list slicing [:]으로 바꾸어 주었더니 python3 로 제출했을때도 맞을 수 있었습니다.

두번째 제출 코드

deepcopy 부분만 다음과 같이 수정하고 다시 제출하였습니다.

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

N, M = map(int, sys.stdin.readline().split())

# 벽 세우고 virus가 퍼진 후 그래프
def virus_BFS(x, y, tempGraph):
    queue = deque()
    queue.append([x, y])
    tempGraph[x][y] = 2
    # 상 하 좌 우
    dx = [1, -1, 0, 0]
    dy = [0, 0, -1, 1]

    while queue:
        v = queue.popleft()

        for i in range(4):
            nx = v[0] + dx[i]
            ny = v[1] + dy[i]
            if nx >= 0 and nx < N and ny >= 0 and ny <M:
                if tempGraph[nx][ny] == 0:
                    tempGraph[nx][ny] = 2
                    queue.append([nx, ny])

    return tempGraph

graph = []
zeroLocate = [] #0의 좌표를 저장한 리스트
virusLocate = [] # 바이러스의 위치를 저장한 리스트
virusGraph = [] # 바이러스가 퍼진 그래프
tempGraph = [] # 그래프의 내용을 변경하기 위한 임시 그래프
combinationsZeroLocate = [] #0의 좌표 중 3개 뽑는 경우의 수를 저장한 리스트
result = 0 # 최종 안전 영역

for i in range(N):
    graph.append(list(map(int, sys.stdin.readline().split())))
    for j in range(M):
        if graph[i][j] == 0:
            zeroLocate.append([i, j])
        elif graph[i][j] == 2:
            virusLocate.append([i, j])

#virusGraph = copy.deepcopy(graph)
virusGraph = [i[:] for i in graph]
combinationsZeroLocate = (list(combinations(zeroLocate, 3)))

for i in combinationsZeroLocate:
    temp = 0
    tempGraph = copy.deepcopy(graph)

    tempGraph[i[0][0]][i[0][1]] = 1
    tempGraph[i[1][0]][i[1][1]] = 1
    tempGraph[i[2][0]][i[2][1]] = 1

    for j in virusLocate:
        #virusGraph = copy.deepcopy(virus_BFS(j[0], j[1], tempGraph))
        virusGraph = [i[:] for i in virus_BFS(j[0], j[1], tempGraph)]

    for j in virusGraph:
        temp += j.count(0)

    result = max(temp, result)

print(result)

 

결과입니다. 마지막으로 pypy3를 제출했더니 python3 보다 4.6배 속도가 빨라진 것을 확인할 수 있었습니다.

다 풀고 이 문제를 검색해본 결과 대부분의 사람들이 백트래킹을 활용해서 푼것을 확인했습니다. 저 또한 다음에는 조합이 아닌 백트래킹을 활용해서 풀어보도록 하겠습니다.