[코딩인터뷰] 백준 15684번

백준 15684번

def is_completed():
    global n
    global h
    global ladder

    for b in range(n):
        s = b
        for a in range(h):
            if 0 < s and ladder[a][s-1]:
                s -= 1
                continue

            if ladder[a][s]:
                s += 1
                continue

        if s != b:
            return False

    return True

def dfs(count, a, b):
    global n
    global h
    global ladder
    global answer

    if is_completed():
        if count < answer:
            answer = count
        return

    if count == 3:
        return

    # 현재 b = 세로선부터 마지막 바로 전 세로선까지만
    # i = 세로선
    for i in range(b, n-1):
        # 첫 점선은 현재 a = 점선부터 시작이지만,
        # 다음 점선부터는 0부터 시작
        t = 0 if b != i else a
        # j = 점선
        for j in range(t, h):

            # 지금 점선에 사다리가 놓여 있다면 통과
            if ladder[j][i]:
                continue

            # 이전 점선에 사다리가 놓여 있다면 통과
            if 0 < i and ladder[j][i-1]:
                continue

            # 다음 점선에 사다리가 놓여 있다면 통과
            if ladder[j][i+1]:
                continue

            # 지금 사다리에 점선을 놓는다.
            ladder[j][i] = True
            # 바로 다음 점선은 놓을 수 없으므로 다다음 점선에 놓는다.
            dfs(count + 1, j, i)
            # 사다리를 회수한다.
            ladder[j][i] = False


# n = 세로선, h = 점선
n, m, h = list(map(int, input().split()))
ladder = [[False] * n for _ in range(h)]
for _ in range(m):
    # a = 점선 b = 세로선
    a, b = map(int, input().split())
    ladder[a-1][b-1] = True

answer = 4
dfs(0, 0, 0)

if answer > 3:
    print(-1)
else:
    print(answer)