파이썬으로 풀어보는 백준 15684번: 사다리 조작 (삼성 A형 기출 문제)

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

15684번: 사다리 조작

 

내 풀이:

def check(lst, res):
    global ans
    for j in range(N):
        x = j
        i = 0
        while i < H:
            if x - 1 >= 0 and lst[i][x - 1]:
                x -= 1
            elif x + 1 <= N - 1 and lst[i][x]:
                x += 1
            i += 1
        if j == x:
            pass
        else:
            return
 
    print(res)
    exit()
 
 
def order1(idx, pre):
    if idx == 1:
        check(pre, 1)
        return
    for i in range(H):
        for j in range(N - 1):
            if pre[i][j]:
                continue
            else:
                pre[i][j] = True
                order1(idx + 1, pre)
                pre[i][j] = False
 
 
def order2(idx, pre):
    if idx == 2:
        check(pre, 2)
        return
    for i in range(H):
        for j in range(N - 1):
            if pre[i][j]:
                continue
            else:
                pre[i][j] = True
                order2(idx + 1, pre)
                pre[i][j] = False
 
 
def order3(idx, pre):
    if idx == 3:
        check(pre, 3)
        return
    for i in range(H):
        for j in range(N - 1):
            if pre[i][j]:
                continue
            else:
                pre[i][j] = True
                order3(idx + 1, pre)
                pre[i][j] = False
 
 
N, M, H = map(int, input().split())
arr = [[False] * (N - 1) for _ in range(H)]
 
for j in range(M):
    a, b = map(int, input().split())
    arr[a - 1][b - 1] = True
 
ans = -1
check(arr, 0)
order1(0, arr)
order2(0, arr)
order3(0, arr)
 
print(ans)

Python3, 시간 초과

사다리에 가로선을 0개 추가하는 경우, 1개 추가하는 경우, 2개 추가하는 경우, 3개 추가하는 경우를 어떻게 구현해야 할지 몰라서 각각의 함수로 만들었다. 3개의 함수를 통해서 사다리를 뽑는 경우는 비효율적일 것으로 예상되어 하나의 함수로 합치는 방향으로 가야 실행시간을 줄일 수 있을 것 같다. 또한 사다리를 완성한 다음 사다리가 문제 조건에 맞는지 시뮬레이션을 다 돌려봐야 하는데 사다리에 가로선을 추가하는 순간 결과를 확인할 수 있다면 시간을 큰 폭으로 줄일 수 있을 것 같다.

 

 

def check(lst, res):
    global ans
    for j in range(N):
        x = j
        i = 0
        while i < H:
            if x-1 >= 0 and lst[i][x-1]:
                x -= 1
            elif x+1 <= N-1 and lst[i][x]:
                x += 1
            i += 1
        if j == x:
            pass
        else:
            return
 
    if ans > res:
        ans = res
 
 
def order(idx, pre, save):
    if idx == 0:
        check(pre, idx)
 
    if idx == 1:
        check(pre, idx)
 
    if idx == 2:
        check(pre, idx)
 
    if idx == 3:
        check(pre, idx)
        return
 
    for i in range(save, H):
        for j in range(N-1):
            if pre[i][j]:
                continue
            if j+1 <= N-2 and pre[i][j+1]:
                continue
            if j-1 >= 0 and pre[i][j-1]:
                continue
            else:
                pre[i][j] = True
                order(idx+1, pre, i)
                pre[i][j] = False
 
 
N, M, H = map(int,input().split())
arr = [[False] * (N-1) for _ in range(H)]
 
for j in range(M):
    a, b = map(int,input().split())
    arr[a-1][b-1] = True
 
ans = 4
order(0, arr, 0)
 
if ans == 4:
    print(-1)
else:
    print(ans)

PyPy3, 2540ms

Python3로는 시간 초과가 나서 PyPy3로 채점하여 정답 처리되었다. 사다리에 가로선을 추가하는 함수를 하나로 합치고 재귀가 돌 때 중복되는 경우를 최대한 줄였다. 또한 내가 설치하려고 하는 위치만 확인했었는데 좌우에 가로선이 있는 경우에도 설치가 불가능하다는 것을 깨닫고 풀이를 수정하였다. Python3로 채점하기 위해서는 알고리즘을 더 최적화할 필요가 있을 것 같다.