[BOJ] 15684. 사다리 조작

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

15684번: 사다리 조작

 

 

1. 해결방법

백트래킹 문제인데 개인적으로 정말 어려웠다.

근데 굉장히 좋은 문제로 생각하는데, 그 이유는 2차원 배열을 자유자제로 조절할 수 있어야 사다리 로직을 구상할 수 있고 가지치기를 해서 연산 횟수를 엄청 줄일 수 있다.

아이디어는 유튜브 링크를 남김. 정말 설명을 잘해주신다.
https://www.youtube.com/watch?v=s5hmaRJ5jN0

 

 

2. 정답코드

(1) 가지치기가 잘 되지 않은 코드 - pypy3 통과

import sys
input = sys.stdin.readline

# input
N, M, H = map(int, input().split())
maps = [[0] * (N + 1) for _ in range(H + 1)]

for i in range(M):
    a, b = map(int, input().split())
    maps[a][b] = 1  # 가로선 시작점
    maps[a][b + 1] = -1 # 가로선 종료점


# check
def check():
    for k in range(1, N + 1):
        point = k
        for i in range(1, H + 1):
            if maps[i][point] == 0:
                continue
            elif maps[i][point] == 1:
                point += 1
            elif maps[i][point] == -1:
                point -= 1
        if point != k:
            return False
    return True


# dfs
def dfs(y, x, cnt):
    global answer

    # 체크
    if check():
        answer = min(answer, cnt)
        return

    if cnt >= 3 or cnt >= answer:
        return

    # 가로선 재귀
    for i in range(1, H + 1):
        for j in range(1, N):
            if maps[i][j] == 0 and maps[i][j + 1] != 1:
                maps[i][j] = 1
                maps[i][j + 1] = -1
                dfs(i, j, cnt + 1)
                maps[i][j] = 0
                maps[i][j + 1] = 0


# main
answer = 4
dfs(1, 1, 0)

print(answer if answer <= 3 else -1)

 

 

(2) 가지치기로 연산 횟수 줄인 코드 - pypy3 통과

import sys
input = sys.stdin.readline

# input
N, M, H = map(int, input().split())
maps = [[0] * (N + 1) for _ in range(H + 1)]

for i in range(M):
    a, b = map(int, input().split())
    maps[a][b] = 1  # 가로선 시작점
    maps[a][b + 1] = -1 # 가로선 종료점


# check
def check():
    for k in range(1, N + 1):
        point = k
        for i in range(1, H + 1):
            if maps[i][point] == 0:
                continue
            elif maps[i][point] == 1:
                point += 1
            elif maps[i][point] == -1:
                point -= 1
        if point != k:
            return False
    return True


# dfs
def dfs(y, x, cnt):
    global answer

    # 체크
    if check():
        answer = min(answer, cnt)
        return
    
    if cnt >= 3 or cnt >= answer:
        return

    # 가로선 재귀
    for i in range(y, H + 1):
        if i == y:
            start = x
        else:
            start = 1
        for j in range(start, N):
            if maps[i][j] == 0 and maps[i][j + 1] != 1:
                maps[i][j] = 1
                maps[i][j + 1] = -1
                dfs(i, j, cnt + 1)
                maps[i][j] = 0
                maps[i][j + 1] = 0


# main
answer = 4
dfs(1, 1, 0)

print(answer if answer <= 3 else -1)