파이썬으로 풀어보는 백준 14502번: 연구소 (삼성 A형 기출 문제)

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

14502번: 연구소

 

내 풀이:

def check(lst):
    global N, M, bn, ans
    new = [arr[_][:] for _ in range(N)]
    for wy, wx in lst:
        new[wy][wx] = 1
 
    res = bn - len(lst)
 
    for vy, vx in virus:
        s = [(vy, vx)]
 
        while s:
            y, x = s[-1]
            for dir in range(4):
                ny = y + dy[dir]
                nx = x + dx[dir]
 
                if 0 <= ny <= N-1 and 0 <= nx <= M-1 and new[ny][nx] == 0:
                    s.append((ny,nx))
                    new[ny][nx] = 2
                    res -= 1
                    break
 
            else:
                s.pop()
 
    if ans < res:
        ans = res
 
 
def wall(idx, lst):
    if len(lst) == 3:
        check(lst)
        return
 
    if idx == len(blank):
        return
    lst.append(blank[idx])
    wall(idx+1, lst)
    lst.pop()
    wall(idx+1, lst)
 
 
N, M = map(int,input().split())
arr = [list(map(int,input().split())) for _ in range(N)]
virus = []
blank = []
bn = 0
ans = 0
 
dy = [-1, 0, 1, 0]
dx = [0, 1, 0, -1]
 
for i in range(N):
    for j in range(M):
        if arr[i][j] == 2:
            virus.append((i, j))
        elif arr[i][j] == 0:
            blank.append((i, j))
            bn += 1
 
wall(0, [])
 
print(ans)

Python3, 5440ms

벽을 무조건 3개 세워야 하는지 모르고 재귀를 통해 새로 설치한 벽이 0개일 때부터 3개 일 때까지를 구현하였다. 먼저 작성한 코드에서 급하게 옳은 답을 출력하기 위해 최소한의 코드만 고쳐서 정답을 맞힌 상태이다. 5440ms라는 긴 시간이 걸렸는데 재귀를 이용하여 벽을 설치하는 방식에서 3중 for문을 이용하는 방식으로 수정하면 시간 단축을 기대할 수 있다.

 

 

def check(lst):
    global N, M, bn, ans
    new = [arr[_][:] for _ in range(N)]
    for wy, wx in lst:
        new[wy][wx] = 1
 
    res = bn - 3
 
    for vy, vx in virus:
        s = [(vy, vx)]
 
        while s:
            y, x = s[-1]
            for dir in range(4):
                ny = y + dy[dir]
                nx = x + dx[dir]
 
                if 0 <= ny <= N-1 and 0 <= nx <= M-1 and new[ny][nx] == 0:
                    s.append((ny,nx))
                    new[ny][nx] = 2
                    res -= 1
                    break
 
            else:
                s.pop()
 
    if ans < res:
        ans = res
 
 
N, M = map(int,input().split())
arr = [list(map(int,input().split())) for _ in range(N)]
virus = []
blank = []
bn = 0
ans = 0
 
dy = [-1, 0, 1, 0]
dx = [0, 1, 0, -1]
 
for i in range(N):
    for j in range(M):
        if arr[i][j] == 2:
            virus.append((i, j))
        elif arr[i][j] == 0:
            blank.append((i, j))
            bn += 1
 
for a in range(bn):
    for b in range(a+1, bn):
        for c in range(b+1, bn):
            check([blank[a], blank[b], blank[c]])
 
 
print(ans)

Python3, 5428ms

예상이 완전히 빗나갔다. 3중 for문을 이용해 벽 3개를 설치할 위치를 고르면 시간을 많이 단축시킬 수 있을 거라 기대했는데 고작 12ms 감소하였다. 위 코딩을 좀 더 최적화 하려면 virus, blank 리스트를 만들기 위해 전역탐색하는 부분을 바꿔주어야하지 않을까 생각한다.