[백준 15684] 사다리 조작 (Python) / G3

문제

15684. 사다리 조작

코드_version1

import sys
input = sys.stdin.readline
def move():
    for i in range(n):
        # 세로선 위치 나타냄
        now = i
        for j in range(h):
            if board[j][now]:
                now += 1
            # 왼쪽 확인
            elif now > 0 and board[j][now-1]:
                now -= 1
        # 끝까지 내려왔을 때 i와 같은지 확인
        if now != i:
            return False
    return True

def dfs(cnt, a, b):
    global res

    if cnt >= res or cnt > 3:
        return

    if move():
        res = min(res, cnt)
        return


    for i in range(a, h):
        # 가로줄의 위치가 재귀 시작한 위치와 같다면
        # b의 전에는 이미 확인한 위치 이므로 b 이후부터 보면 된다
        if i == a:
            now = b
        else:
            now = 0
        # 마지막 세로줄은 볼 필요 없음.
        for j in range(now, n-1):
            # 가로선이 서로 연속하는 경우는 없다
            if board[i][j] == 0 and board[i][j+1] == 0:
                if j > 0 and board[i][j-1]:
                    continue
                board[i][j] = 1
                # 가로선 연속 안하므로 다다음 부터 확인
                dfs(cnt+1, i, j+2)
                board[i][j] = 0



n, m, h = map(int,input().split())
# board[a][b] = 1이면 b와 b+1 세로선을 a번 점선 위치에서 연결을 의미함
board = [[0]*n for _ in range(h)]
for _ in range(m):
    a, b = map(int,input().split())
    board[a-1][b-1] = 1

res = float('inf')
dfs(0,0,0)
if res > 4:
    print(-1)
else:
    print(res)

코드 설명

사다리를 보드판이라고 생각해서
board[a][b] = 1이면 b와 b+1 세로선을 a번 점선 위치에서 연결을 의미한다.
그래서 0인 보드판 중에 0인 위치 중에 고르는 백트래킹을 구현해주었다.

문제 조건에 정답이 3보다 큰 값이면 -1을 출력하라고 했으니까 3보다 큰 값은 계산을 하지 않아도 되므로 가지치기 조건으로 넣어주었다.

보드판이 i번 세로선의 결과가 i번이 나와야하는 조건을 만족하는지 확인하기 위해 move라는 함수를 만들어서 자신의 위치에 대해 양 옆으로 사다리가 있는지 확인하여 이동시켜주었다.

코드_version2

import sys
input = sys.stdin.readline
from itertools import combinations

def move():
    for i in range(n):
        # 세로선 위치 나타냄
        now = i
        for j in range(h):
            if board[j][now]:
                now += 1
            # 왼쪽 확인
            elif now > 0 and board[j][now-1]:
                now -= 1
        # 끝까지 내려왔을 때 i와 같은지 확인
        if now != i:
            return False
    return True


n, m, h = map(int,input().split())
# board[a][b] = 1이면 b와 b+1 세로선을 a번 점선 위치에서 연결을 의미함
board = [[0]*n for _ in range(h)]
for _ in range(m):
    a, b = map(int,input().split())
    board[a-1][b-1] = 1

valiable = []
res = 4
for i in range(h):
    for j in range(n-1):
        if board[i][j] == 0:
            valiable.append((i, j))

for cnt in range(4):
    for lst in combinations(valiable, cnt):
        for a, b in lst:
            board[a][b] = 1
        if move():
            res = min(res, cnt)
            for a, b in lst:
                board[a][b] = 0
            break
        for a, b in lst:
            board[a][b] = 0
    # res 값이 바꼈다면 그것이 최소값
    if res != 4:
        break

if res > 3:
    print(-1)
else:
    print(res)

코드 설명

조합을 이용하여 구현해주었다.
보드판이 i번 세로선의 결과가 i번이 나와야하는 조건을 만족하는지 확인하는 함수는 위의 코드를 그대로 사용해주었고,

0~3개를 뽑는 조합을 만들어서
만약 해당 조합이 res값을 변경시키면 그게 가로선 개수의 최소값이므로 cnt에 해당하는 for문을 break 해주었다.