백준 15684번: 사다리 조작 (Python, PyPy3)

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

15684번: 사다리 조작

접근

사다리를 matrix로 저장하고, 이미 존재하는 가로 사다리들을 입력해준다. 가로 사다리를 추가 가능한 위치들 중 3군데를 선택하여 가로 사다리들을 추가해주고, i번째 출발지에서 i번째 도착지로 가는지 체크하여 답을 얻을 수 있다.

Python으로 시간 내에 완성하는 것에 실패하고, PyPy3으로 정답 완성할 수 있었다.

코드

N, M, H = map(int, input().split())
ladder = [[0] * H for _ in range(N - 1)]
for i in range(M):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    ladder[b][a] = 1
    if b < N - 2:
        ladder[b + 1][a] = -1
    if 0 < b:
        ladder[b - 1][a] = -1
possible_ladder = []
for i in range(N - 1):
    for j in range(H):
        if ladder[i][j] == 0:
            possible_ladder.append((i, j))
min_val = [4]


def ladder_down(s):
    # s에서 출발하는 사다리가 도착하는 위치를 리턴
    p = 0
    while p < H:
        if s < N - 1 and ladder[s][p] == 1:
            s += 1
        elif 0 < s and ladder[s - 1][p] == 1:
            s -= 1
        p += 1
    return s


def check():
    # i번 출발지-i번 도착지 연결이 이루어졌는지 확인하여 리턴
    flag = True
    s = 0
    while flag and s < N:
        if s != ladder_down(s):
            flag = False
        s += 1
    return flag


def solve(depth, position_list, index):
    if min_val[0] <= depth or 3 < depth:
        # 이미 구해진 최대 사다리 개수보다 클 경우, 사다리를 3개 이상 사용해야 할 경우 계산 종료
        return
    if check():
        # 사다리가 조건을 만족했을 경우, 최소 사다리 개수 갱신
        min_val[0] = min(min_val[0], depth)
    for i in range(index + 1, len(position_list)):
        r, c = position_list[i]
        # 사다리가 있을 수 없는 조건 continue
        if r < N - 2 and ladder[r + 1][c] == 1:
            continue
        if 0 < r and ladder[r - 1][c] == 1:
            continue
        ladder[r][c] = 1
        solve(depth + 1, position_list, i)
        ladder[r][c] = 0


solve(0, possible_ladder, -1)
if min_val[0] == 4:
    print(-1)
else:
    print(min_val[0])

더 생각해 볼 것?

...

코드나 내용 관련 조언, 부족한 점 및 질문 언제든 환영합니다!