[백준] 15684번 - 사다리 조작

15684번: 사다리 조작

해당 문제는 완전탐색 문제로 놓을 수 있는 모든 사다리를 놓아보면서 사다리를 연결 했을때, 자기자신이 연결되는지 확인하는 백트래킹 + 완전탐색 + 구현 문제이다. 사다리를 놓을때에는 연속해서 놓이지 않게 해야하며 자기자신이 연결되는지 확인하는 구현, 추가해야하는 사다리의 개수가 넘어가면 백트래킹 하면 된다.

가능한 사다리를 놓아보는 조합을 구현하는것이 제일 복잡 했습니다.

import sys
input = sys.stdin.readline

N, M, H = map(int, input().split())
sa = [[False for _ in range(H+1)] for _ in range(N+1)]

for _ in range(M):
    a, b = map(int, input().split())
    sa[b][a] = True # b, b+1의 세로선을 높이 a의 위치에서 연결함.

def solution(depth, x,y):
    if check():
        return depth

    if depth >= 3:
        return depth + 1

    ans = 4
    for h in range(x, H+1):
        if h == x:
            k = y  # 행이 변경되기 전에는 가로선을 계속해서 탐색
        else:
            k = 1  # 행이 변경될 경우 가로선 처음부터 탐색
        for c in range(k, N):
            if not sa[c][h] and not sa[c-1][h] and not sa[c+1][h]: # 현재위치에서 사다리가 연결되어있지 않다면
                sa[c][h] = True
                ans = min(solution(depth+1, h, c+2), ans)
                sa[c][h] = False

    return ans

def check():
    for i in range(1, N+1):
        h = 1
        cur = i
        while H >= h:
            if sa[cur][h] or sa[cur-1][h]:
                if sa[cur][h]:
                    cur += 1
                else:
                    cur -= 1

            h += 1
        if cur != i:
            return False

    return True

answer = solution(0,1, 1)
if answer == 4:
    print(-1)
else:
    print(answer)