연구소

문제 파악

주어진 연구소에서 벽을 3개 세워서 바이러스로부터 안전한 영역의 최대 크기를 구하는 문제

14502번: 연구소

접근 방법

1. 주어진 연구소 상태에서 바이러스가 있는 위치를 찾는다
2. 벽을 세우는 모든 가능한 경우의 수를 탐색한다.
3. 각 경우마다 벽을 세우고, 바이러스를 퍼뜨린 뒤 안전 영역의 크기를 계산한다
4. 안전 영역의 최대 크기를 반환한다.

코드 구현

import sys
from copy import deepcopy
from collections import deque

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

board = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]

# 벽세우기
# 바이러스 퍼뜨리기
# 안전지대 확인

virus_cord = []
results = []

def lab():
    find_virus()
    make_wall(0)
    print(max(results))
    return max(results)

def virus_bfs():
    blank = deepcopy(board)
    dx = [-1, 1, 0, 0]
    dy = [0, 0, -1, 1]

    q = deque()
    for x, y in virus_cord:
        q.append((x, y))

    while q:
        cur_x, cur_y = q.popleft()
        for i in range(4):
            next_x = cur_x + dx[i]
            next_y = cur_y + dy[i]
            if next_x >= 0 and next_x < N and next_y >= 0 and next_y < M:
                if blank[next_x][next_y] == 0:
                    blank[next_x][next_y] = 2
                    q.append((next_x, next_y))

    # 안전지대 계산
    cnt = sum(row.count(0) for row in blank)
    results.append(cnt)

def find_virus():
    for x in range(N):
        for y in range(M):
            if board[x][y] == 2:
                virus_cord.append((x, y))
                
# 재귀적으로 구현 시간복잡도 초과
#def make_wall(wall):
#    if wall == 3:
#        virus_bfs()
#        return
#
#    for i in range(N):
#        for j in range(M):
#            if board[i][j] == 0:
#                board[i][j] = 1
#                make_wall(wall + 1)
#                board[i][j] = 0

def make_wall():
    # 벽을 세울 수 있는 후보 위치 찾기
    candidates = [(i, j) for i in range(N) for j in range(M) if board[i][j] == 0]

    # 벽을 세울 후보 위치 중에서 3개를 선택하여 벽을 세우는 모든 경우의 수 고려
    for walls in combinations(candidates, 3):
        # 벽 세우기
        for wall_x, wall_y in walls:
            board[wall_x][wall_y] = 1
        # 바이러스 퍼뜨리고 안전 지역 개수 세기
        virus_bfs()
        # 다시 벽 제거 (다음 경우의 수를 위해)
        for wall_x, wall_y in walls:
            board[wall_x][wall_y] = 0

lab()

배우게 된 점

• 백트래킹을 재귀적으로 구현하면 호출 관련 오버헤드가 많이 발생하고 실행시간을 증가시킨다, 그렇기 때문에 최적화를 하려면 itertools에 combinations을 사용해야한다.
• deepcopy를 임포트해서 사용하는것도 실행 속도 측면에서 불리하다. 슬라이싱을 사용하면 실행시간을 줄일수 있다.

질문

백준에 Python3로 제출시 시간초과로 실패하나, PyPy3로 제출시 2716ms초로 무사통과 됩니다.

1. 이럴때는 둘 중 하나만 맞았고 하나는 틀렸다고 하면 틀린 소스라고 생각하고 다른 로직으로 풀어야 할까요?

2. 제 코드에서 어떤부분을 최적화 해야 Python3로 제출했을때 통과 할수 있을까요?

피드백

1. PyPy3는 코드가 길어지는 상황에서 Python3보다 실행속도를 개선해주기 때문에 Python3로는 시간초과가 발생하지만, PyPy3로는 통과될 수 있습니다. 코테를 보실 때, Python3를 기준으로 보실 확률이 높기 때문에 Python3 통과를 기준으로 생각해서 코드를 작성해주시면 좋을 것 같습니다.

2. 2가지 포인트를 짚어드리겠습니다. 이 부분을 참고하셔서 코드를 수정해보시면 좋겠네요.

   1. deepcopy

      deepcopy가 깊은 복사를 위해서 따로 import를 하시는데, 사실 실행 속도 측면에서는 매우 불리합니다. 따라서 deepcopy를 사용하기보다는 blank = board[:] 로 slicing을 활용해주시면 실행시간을 줄일 수 있습니다. 그래서 deepcopy보다 [:]를 사용하시는 것을 매우 추천드립니다!

   2. make_wall 함수 구현

      바이러스 위치 세 곳에 대한 조합을 만들어내시는 것은 매우 올바른 접근입니다. 하지만, 재귀로 구현하는 것은 함수 호출이 많이 실행되기 때문에 호출 관련 오버헤드가 많이 발생하고, 실행 시간을 길게 만드는 원인이 되기도 합니다. 그래서 저는 itertools의 combinations를 사용하시는 것을 추천드립니다. combinations는 기존의 재귀적 접근보다 최적화된 방식을 사용하기 때문에 실행 시간을 줄일 수 있습니다.