[백준알고리즘] 15684번: 사다리 조작 -Python

[백준알고리즘] 15684번: 사다리 조작 -Python

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

15684번: 사다리 조작

Python3로는 시간 초과가 난다.

 

브루트 포스문제인데 최근에 또다시 브루트 포스 문제에 약해졌다. 이게 최근 들어 알고리즘 풀기가 너무 힘든데 뭔가 귀찮아지면서 하기 싫어지는 것도 큰 것 같다. 다시 마음가짐을 해야지..

 

아무튼 이번 문제는 처음에 문제를 이해하는 데도 오래 걸렸다. n은 세로줄의 수, h는 가로줄의 수다. 여기서 m은 가로줄이 아닌 현재 두 세로줄을 연결하는 가로 한 칸을 의미한다.

 

그래서 m의 개수가 0 <= m <= (n-1)*h인 것이다. 가로 막대를 최대 3개까지 추가해서 출발점과 도착점이 같은 열리도록 해야 한다.

 

그러면 풀어야 하는 방법은 다른 게 생각 안 나니 브루트 포스 방식밖에 없다. 처음에는 두 열 사이에 존재하는 가로 막대가 모두 짝수이면 가능한가 생각해봤는데, 모두 홀수여도 가능하고, 모두 짝수임에도 불가능한 경우를 찾았어서 포기했었다.

 

 

브루트 포스 방식으로 하려면 주어진 제한사항만 지키면 쉽게 가능하다. 우선 모든 좌표를 돌면서 놓을 수 있는 곳에 하나씩 넣어보고 검사하는 과정을 수행해야 한다. 가로 막대를 놓을 수 있는 칸은 현재 막대가 놓여있지 않으며, 가로 막대 롤 놓았을 때 연속적으로 놓이는 'ㅡㅡ'와 같이 막대 두개가 놓여지는 경우이다.

 

또, 사다리가 원하는 방식대로 출발 열과 도착 열이 일치하는지 막대를 하나만 놓았을 때, 두개를 놓았을 떄, 세개를 놓았을 떄 모두 검사를 해야 한다. 이 부분을 간단하게 해 주기 위해서 재귀 호출을 사용했다.

 

 

이렇게 재귀로 돌아가는 부분이 엄청 많다 보니.. 적은 범위로도 시간 초과가 당연히 날 것이다.. 그런 와중에 PyPy3로 통과하는 게 신기하다. 그나마 범위가 많이 크지는 않아서 그런 것 같다.

from sys import exit

n, m, h = map(int, input().split())
if m == 0:
    print(0)
    exit()

bridge = [[False] * n for _ in range(h)]
for _ in range(m):
    a, b = map(int, input().split())
    bridge[a-1][b-1] = True

def check():
    for start in range(n):
        k = start
        for i in range(h):
            if bridge[i][k]:
                k += 1
            elif k > 0 and bridge[i][k-1]:
                k -= 1
        if start != k:
            return False
    return True

def bf(cnt, x, y):
    global ans
    if check():
        ans = min(ans, cnt)
        return
    elif cnt == 3 or ans <= cnt:
        return

    for i in range(x, h):
        k = y if i == x else 0
        for j in range(k, n-1):
            if not bridge[i][j] and not bridge[i][j+1]:
                bridge[i][j] = True
                bf(cnt+1, i, j+2)
                bridge[i][j] = False

ans = 4
bf(0, 0, 0)
print(ans if ans < 4 else -1)

 

잘못된 점이나 부족한 점 지적해주시면 감사하겠습니다