[파이썬 PYTHON] 백준 15684번 【사다리 조작】

---

import sys

# 예제 입력
N, M, H = map(int, sys.stdin.readline().split())
ladders = [list(map(int, sys.stdin.readline().split())) for _ in range(M)]
_map = [[0] * N for _ in range(H)]

# 사다리 정보 저장
# 왼쪽은 1 오른쪽은 -1로 저장
for ladder in ladders:
    ladderR = ladder[0] - 1
    ladderC = ladder[1] - 1
    _map[ladderR][ladderC] = 1
    _map[ladderR][ladderC + 1] = -1


# 모든 i번 결과가 i번 인가?
def isEqual():
    for i in range(N):
        location = i
        for step in range(H):
            if _map[step][location] == 1:
                location += 1
            elif _map[step][location] == -1:
                location -= 1
        if location != i:
            return False
    return True


plusNum = 0
ans = 4


def bt():
    global plusNum
    global ans

    if plusNum < ans and isEqual():
        ans = plusNum
        return
    if plusNum == 3:
        return

    for i in range(H):
        for j in range(N - 1):
            if abs(_map[i][j]) == 1 or abs(_map[i][j + 1]) == 1:
                continue
            _map[i][j] = 1
            _map[i][j + 1] = -1
            plusNum += 1
            bt()
            _map[i][j] = 0
            _map[i][j + 1] = 0
            plusNum -= 1


bt()
print(-1) if ans == 4 else print(ans)

 

문제 접근 방법

1. 세로선이 N개 이고 가로선을 놓을 수 있는 갯수는 H이므로 N*H 크기의 2차원 배열을 _map으로 사용

2. 백트래킹을 이용해서 사다리를 놓을 수 있는 곳에 넣어보고 isEqual() 함수를 통해서 i번에서 출발한 것이 i번에 도착하는지 확인

3. 사다리 위치 저장 시, 왼쪽에서 오른쪽으로 가는 것은 1, 오른쪽에서 왼쪽으로 가야하는 것은 -1로 저장했다. 따라서 1을 만나면 출발 위치(i) 에서 +1 해야하고 -1을 만나면 -1을 한다.

4. 사다리는 연속해서 놓을 수 없기 때문에 백트래킹 시 조건문 활용

5. 백트래킹 내, 조건문을 잘 활용해야 시간초과를 막을 수 있다.

     5.1 사다리 갯수가 isEqual() 함수를 지나쳤는데 3개라면 사다리 갯수가 4개 이상이 무조건 필요하다는 의미이므로 더 로직을 돌릴 필요가 없다. ( 문제 조건에서 3개보다 크면 -1을 출력하라고 했으므로) 

     5.2 앞서 먼저 isEqual()을 만족해서 갱신된 사다리의 갯수인 ans보다 작은 경우에만 isEqual() 함수로 확인해본다.