[BOJ 15684] 사다리 조작(Python)

문제

사다리 조작

---

문제 해설

문제를 이해하는데 오래걸렸던 문제입니다. 크게 생각하면 두가지 조작을 해야합니다.

• 사다리 놓기
• 자신의 번호로 가는지 확인

사다리를 놓으려면 사다리를 놓을수 있는지 확인해야합니다. 이미 연결되어있는 경우는 불가합니다. 저는 연결정보가 들어있는 2차원 리스트를 활용했고 어느쪽으로 연결되어있는지 확인하기 위해 정수형을 활용했지만 boolean으로 활용해도 상관 없을 것 같습니다.

• 시간 초과
  pypy3로 제출했을때 시간 초과가 나지 않습니다..
  

---

풀이 코드

n, m, h = map(int, input().split())
connect = []  # 연결상태
flag = False  # 3보다 크면 True
for i in range(h + 1):
    connect.append([x for x in range(n + 1)])

for i in range(m):
    a, b = map(int, input().split())
    connect[a][b] = b + 1  # a->b
    connect[a][b + 1] = b  # b->a

# 각자 자기 번호로 가는지 검증
def play():
    for i in range(1, n + 1):
        now = i
        for j in range(1, h + 1):
            now = connect[j][now]
        if now != i:  # 자기 자신의 번호
            return False
    return True


def dfs(depth, goal, x, y):
    if depth == goal:  # 다리를 개수만큼 놓으면
        if play():  # 검증을 시작
            print(goal)
            exit()
        return
    for i in range(1, h + 1):
        for j in range(1, n):
            # 다리가 연결이 없는지 확인 후 연결
            if connect[i][j] == j and connect[i][j + 1] == j + 1 and (i >= x or j <= y):
                connect[i][j] = j + 1
                connect[i][j + 1] = j
                dfs(depth + 1, goal, i, j)
                connect[i][j] = j
                connect[i][j + 1] = j + 1


for i in range(0, 4):  # 최대 길이 3만큼만 연결시켜봄.
    dfs(0, i, 0, 0)
print("-1")