[Python] 백준 15684 : 사다리 조작

15684번: 사다리 조작

풀이 방법

• i에서 출발했을 때, 어디서 끝나는지 return해줄 함수가 필요하다.
• board[a][b] = 1은 a번 점선 위치로 b에서 b+1로 갈 수 있음을 의미하고, board[a][b] = -1은 a번 점선 위치로 b에서 b-1로 갈 수 있음을 의미한다.
• board[a][b] = 0이라면 a번 점선 위치로 b세로줄에서 갈 수 있는 곳이 없음을 의미한다.
• 브루투포스를 이용해서 아직 연결되지 않은 가로줄 중 3개 이하를 뽑았을 때, i에서 시작하면 i로 끝나는지 검사한다.
• 아직 연결되지 않은 가로줄을 미리 배열에 저장하고 브루트 포스의 loc를 이용해 접근하면 더 빠르다.

전체 코드

def go(start):
    for i in range(1, h+1):
        if board[i][start] == 1:
            start += 1
        elif board[i][start] == -1:
            start -= 1
    return start

def dfs(loc, cnt):
    global answer
    if answer <= cnt:
        return
    for i in range(1, n+1):
        if i != go(i):
            break
    else:
        answer = min(answer, cnt)
        return
    if loc >= len(arr) or cnt >= 3: return
    for i in range(loc, len(arr)):
        a, b = arr[i]
        if board[a][b] == 0 and board[a][b+1] == 0:
            board[a][b] = 1
            board[a][b+1] = -1
            dfs(i+1, cnt+1)
            board[a][b] = 0
            board[a][b+1] = 0

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

arr = []
for a in range(1, h+1):
    for b in range(1, n):
        if not board[a][b] and not board[a][b+1]:
            arr.append((a, b))
answer = float('inf')
dfs(0, 0)
if answer == float('inf'):
    print(-1)
else:
    print(answer)