245. 사다리 조작

백준

1.Python

import sys
from collections import deque
input = sys.stdin.readline

#n: 열, h:행
n, m, h = map(int, input().split())
ladder = [[0] * n for _ in range(h)]

for _ in range(m):
   #a:행, b:열
    a, b = map(int, input().split())
    ladder[a - 1][b - 1] = 1

ans = 4

def check():
    for i in range(n):
        k = i
        for j in range(h):
            if ladder[j][k]:
                k += 1
            elif k > 0 and ladder[j][k-1]:
                k -= 1
        if i != k:
            return False
    return True
        
def solve(cnt, x, y):
    global ans
    if ans <= cnt:
        return
    if check():
        ans = min(ans, cnt)
        return
    if cnt == 3:
        return
    for i in range(x, h):
        k = y if i == x else 0
        for j in range(k, n-1):
            if ladder[i][j]:  #사다리가 연결되어 있다면 (i, j+2)
                j += 1
            else:
                ladder[i][j] = 1 #사다리 만들기
                solve(cnt+1, i, j+2) #(i, j+2)로 이동
                ladder[i][j] = 0

solve(0, 0, 0)
print(ans if ans < 4 else -1)

        

시간 감소

import sys
input = sys.stdin.readline

def check():
    global n, h
    for i in range(n):
        y = i
        for k in range(h):
            y += ladder[k][y]
        if y != i:
            return False
    return True

def dfs(index,cnt,limit):
    global n, h, result
    if limit == cnt:
        if check():
            result = limit
        return
    for ind in range(index, n*h):
        x = ind // n
        y = ind % n
        if y == n - 1:
            continue
        if not ladder[x][y] and not ladder[x][y + 1]:
            ladder[x][y] = 1
            ladder[x][y+1] = -1
            dfs(ind + 2,cnt + 1,limit)
            if result != 4:
                return
            ladder[x][y] = 0
            ladder[x][y + 1] = 0


n, m, h = map(int,input().split())

if m == 0:
    print(0)
else:
    result = 4
    call = 0
    ladder = [[0]*n for _ in range(h)]
    for _ in range(M):
        row,node = map(int, input().split())
        ladder[row-1][node-1] = 1
        ladder[row-1][node] = -1

    if check():
        print(0)
    else:
        for k in range(1,4):
            dfs(0,0,k)
            if result != 4:
                break
        if result != 4:
            print(result)
        else:
            print(-1)

설명

N, M, H = list(map(int, input().split()))

map_list = [[0] * (N-1) for _ in range(H)]
total_move = 4

#세팅되어 있는 맵 입력하기
for _ in range(M):
    a, b = list(map(int, input().split()))
    map_list[a-1][b-1] = 1

#1번부터 시작해서 1번에 1번, 2번에 2번,,, 이 맞나 확인하는 메소드
def go():
    for i in range(N):
        x, y = 0, i #출발 좌표 저장
        orig_y = y #나중에 맞나 비교를 위해 원래 좌표 저장
        while(True):
            #down
            x, y = x+1, y
            if x == H+1:
                break
            #check left
            if x-1 >= 0 and y-1 >= 0 and map_list[x-1][y-1] == 1:
                x, y =  x, y-1
                continue
            #check right
            if x-1 >= 0 and y < N-1 and map_list[x-1][y] == 1:
                x, y = x, y+1
                continue
        #도착했는데 안 같다면 
        if orig_y != y:
            return False
    return True

#추가하는 사다리 갯수별로 함수를 돌릴 것이다.
def solution(cnt, start, limit):
    global total_move
    #써야될 사다리 갯수 다 썼을 때
    if cnt == limit:
        #사다리 타봤는데 1번째에 1번이 안나온다면
        if go() == False:
            return False
        #사다리 탔는데 잘 된다면
        else:
            #최솟값만 골라내기 위해
            if total_move > limit:
                total_move = limit
            return True
    
    #그전에 다리를 놓으면서 재귀 들어갔던 행부터 시작
    for i in range(start, H):
        #열의 마지막까지 돌면서
        for j in range(N-1):
            #다리가 이미 놓아져있다면
            if map_list[i][j] == 1:
                continue
            #다리가 안 놓아져있는데
            if map_list[i][j] == 0:
                #그 왼쪽에 다리가 놓아져있어
                if j-1 >= 0 and map_list[i][j-1] == 1:
                    continue
                #그 오른쪽에 다리가 놓아져있어
                if j+1 <= N-2 and map_list[i][j+1] == 1:
                    continue
            #나의 맵에다가 1을 넣어주고(다리가 놓여져있다)
            map_list[i][j] = 1
            #다리를 마지막으로 놨던 행부터 다시 시작
            if solution(cnt+1, i, limit):
                return True
            #백트래킹의 방법
            map_list[i][j] = 0

#다리 0개부터 돌려보자
for i  in range(4):
    flag = solution(0, 0, i)
    if flag:
        break
    
if total_move == 4:
    print("-1")
else:
    print(total_move)



#출처: https://coreenee.github.io/2020/07/02/%EB%B0%B1%EC%A4%8015684(%EC%82%AC%EB%8B%A4%EB%A6%AC-%EC%A1%B0%EC%9E%91)/