[백준/python] 15684번 사다리 조작

https://www.acmicpc.net/problem/15684

15684번: 사다리 조작

구현 + 백트래킹 + 브루트포스 문제다.

 

사다리의 가로줄과 세로줄을 각각 x좌표 y좌표라고 생각하고 풀면 편할 것이다.

우선 입력을 받으면서, 가로선이 그려진 좌표를 표시해준다. (가로선이 그려질 때 (x,y)와 (x,y+1)를 잇게 되는데, 이 두 좌표를 모두 1로 표시하고 푸는 방법도 있으니 참고!)

 

그리고나서 탐색을 시작하는데, 매 탐색마다 i번 라인에서 출발하여 도착 결과가 i번 인지 확인해준다. 이때 출발한 라인의 값을 따로 저장해주고, 사다리를 따라 내려가면서 마지막 도착이 처음 출발한 라인과 같은지만 비교해주면 된다.

 

지금까지 그린 가로선이 3개라면 더 탐색할 필요 없으므로 return하고, 만약 현재 y좌표가 세로선을 넘어갔다면 x좌표를 1 증가하고 y를 다시 0으로 되돌린다.

 

현재 위치에서 가로선을 그릴 수 있는지 판단할 때, 항상 양 옆을 확인해주어야한다.

탐색도 인자로 건네받은 (x,y)좌표에서부터 시작하므로, 만약 가로선을 그리지 못하고 다음 줄로 넘어가게 되었을 때 y값도 앞으로 땡겨와야한다는 점을 유의해주면 금방 풀 수 있는 문제이다.

import sys
input = sys.stdin.readline

def check():
    # i번 라인에서 출발
    for i in range(n):
        temp = i    
        for j in range(h):
            if graph[j][temp]: #만약 가로선이 있다면
                temp += 1
            elif temp > 0 and graph[j][temp - 1]: # 맨 왼쪽 라인이 아니면서 왼쪽 라인을 잇는 가로줄이 있다면
                temp -= 1
        if temp != i:
            return False
    return True

def dfs(cnt, x, y):
    global ans
    
    if check(): 
        ans = min(ans, cnt)
        return
    
    if cnt == 3: return
    
    if y>=n-1:
        x+=1
        y=0
    
    for i in range(x,h):
        if i==x: y=0
        for j in range(y,n-1):
            if graph[i][j] == 0 and cnt+1 < ans and graph[i][j+1]!=1 :# 가로줄이 없고 더 만들 수 있을 때
                if j>0 and graph[i][j-1] ==1:
                    continue
                graph[i][j]=1
                dfs(cnt+1,i,j+2)
                graph[i][j]=0
                    
n,m,h = map(int, input().split())
graph = [[0] * n for _ in range(h)]

for _ in range(m):
    a, b = map(int, input().split())
    graph[a - 1][b - 1] = 1
    
ans = 4

if m==0:
    print(0)
else:
    dfs(0,0,0)
    print(ans if ans <= 3 else -1)