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

0.  문제 링크

 

 

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

15684번: 사다리 조작

---

1.  풀이 방법

 

 

1. 입력을 받을 때, 사다리가 있는 곳이라면 왼쪽을 1, 오른쪽을 -1로 설정했다.
2. 이제 사다리를 놓을 수 있는 곳을 후보군으로 찾는다.
3. 이것을 이용해서 백트래킹 재귀를 돌리면 끝. 매우 간단하다.

추가로 각 라인

---

2.  코드

 

 

import sys
input = sys.stdin.readline


def solve(total, next):
    global minimum

    if total >= minimum:        # 기존의 최솟값 보다 작으면 패스해야함
        return
    
    if check():
        minimum = total
        return
    else:
        for i in range(next, len(candidate)):
            y, x = candidate[i]
            if maps[y][x] == 0 and maps[y][x + 1] == 0:     # 현재와 오른쪽에 라인이 없어야 함.
                maps[y][x] = 1
                maps[y][x + 1] = -1

                solve(total + 1, i + 1)

                maps[y][x] = 0
                maps[y][x + 1] = 0


def check():
    for x in range(1, n + 1):       # 전체 라인에 대해서 검사해야 함
        cur = x
        for y in range(1, h + 1):
            if maps[y][cur] == 1:
                cur += 1
            elif maps[y][cur] == -1:
                cur -= 1

        if x != cur:        # 라인 하나라도 틀리면 False임
            return False
            
    return True
                

if __name__ == "__main__":
    n, m, h = map(int, input().split())
    maps = [[0] * (n + 1) for _ in range(h + 1)]
    candidate = []
    minimum = 4

    for _ in range(m):
        y, x = map(int, input().split())
        maps[y][x] = 1      # 오른쪽으로
        maps[y][x + 1] = -1     # 왼쪽으로

    for y in range(1, h + 1):
        for x in range(1, n):       # 오른쪽만 볼거임
            if maps[y][x] == 0 and maps[y][x + 1] == 0:        # 오른쪽에 라인이 없어야 함
                candidate.append((y, x))

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

---

3.  마무리