[CLASS 4]백준 14502번 - 연구소

14502번 : 연구소

 

일단 이 문제를 처음 보고 어떻게 풀지 전혀 몰랐었다. BFS 인건 확실한데, 어떤 기준으로 벽을 세워야 할지 전혀 알 수가 없었다. 그래서 고민 끝에 풀이를 검색해 봤는데, 그냥 브루트포스로 벽을 다 세워보는 것이었다....

 

내 코드(python3 시간 초과):

# dawitblog.tistory.com
from sys import stdin
from collections import deque
from copy import deepcopy
input = stdin.readline

move = [(1,0),(-1,0),(0,1),(0,-1)]

def find():
    global maxSafe
    q = deque(virus)
    copyMat = deepcopy(mat)

    while q:
        vr, vc = q.popleft()

        for dr,dc in move:
            nr = vr + dr
            nc = vc + dc

            if 0<= nr < R and 0<= nc < C and not copyMat[nr][nc]:
                copyMat[nr][nc] = 2
                q.append((nr,nc))

    safe = 0
    for r in range(R):
        for c in range(C):
            if not copyMat[r][c]:
                safe += 1

    if safe > maxSafe:
        maxSafe = safe

def wall(count):
    if count == 3:
        find()
        return

    for r in range(R):
        for c in range(C):
            if not mat[r][c]:
                mat[r][c] = 1
                wall(count+1)
                mat[r][c] = 0

R,C = map(int,input().split())
mat = []
virus = []
for r in range(R):
    l = list(map(int,input().split()))
    for c in range(C):
        if l[c] == 2:
            virus.append((r,c))
    mat.append(l)

maxSafe = 0
wall(0)
print(maxSafe)

 

이게 처음으로 작성한 코드인데, pypy3 에서는 통과하지만 python3에서는 시간 초과를 맞았다. 그래서 어디에서 시간을 줄일지 봤는데, 벽을 세우는 곳을 찾는 과정에서 불필요한 중복 연산이 있는것 같아서 그냥 조합으로 바꿔버렸다.

 

내 코드:

# dawitblog.tistory.com
from sys import stdin
from collections import deque
from copy import deepcopy
from itertools import combinations
input = stdin.readline

# 4방향 이동
move = [(1,0),(-1,0),(0,1),(0,-1)]

# BFS
def find(newWalls):
    global maxSafe
    # 큐 선언 후 바이러스 초기 위치로 초기화
    q = deque(virus)
    # 임시 리스트 복사
    copyMat = deepcopy(mat)

    # 벽 세우기
    for wallR,wallC in newWalls:
        copyMat[wallR][wallC] = 1

    while q:
        # 바이러스 좌표
        vr, vc = q.popleft()

        for dr,dc in move:
            # 추가되는 바이러스 좌표
            nr = vr + dr
            nc = vc + dc

            if 0<= nr < R and 0<= nc < C and not copyMat[nr][nc]:
                copyMat[nr][nc] = 2
                q.append((nr,nc))

    # 남아있는 안전구역 확인
    safe = 0
    for r in range(R):
        for c in range(C):
            if not copyMat[r][c]:
                safe += 1

    # 최고기록 갱신
    if safe > maxSafe:
        maxSafe = safe

    

R,C = map(int,input().split())
mat = []
virus = []
space = []
for r in range(R):
    l = list(map(int,input().split()))
    # 초기 바이러스,빈 공간 위치 기억
    for c in range(C):
        if l[c] == 2:
            virus.append((r,c))
        elif l[c] == 0:
            space.append((r,c))
    mat.append(l)

maxSafe = 0
# 벽 새울 곳 조합으로 구하기
newWalls = list(combinations(space,3))
for newWall in newWalls:
    find(newWall)
# 출력
print(maxSafe)

 

조합으로 하면 코드짜기도 편하고 중복도 없어서 아주 편안~ 하게 코드를 짤 수 있다. 다만 라이브러리를 썼다는 것이 조금 불편하긴 하다.