[백준] 사다리 조작

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

15684번: 사다리 조작

dfs를 이용하는 문제입니다.

 

우선 문제부터 간단하게 요약하면, 

사다리가 주어지는데, 이 사다리에 사다리를 3개까지 추가해서 각각의 사다리가 도착지점도 번호가 같도록 만드려 하는데, 필요한 사다리의 최소갯수를 구해야 하는 문제입니다. 

 

<Solution>

DFS를 이용해야 합니다. 

로직은 아래와 같습니다. 

1. 각 사다리를 놓을 수 있는 지점에 사다리를 하나씩 놓아본다.(중복된 경우의 수 안하도록 주의) 2. 만약 놓았을 때 결과가 올바르게 나오면, 최솟값을 갱신하면서 최솟값을 찾는다.

 

실제 구현은 아래와 같습니다. 

import sys

def ans_ladder(ladder) -> bool:
    current_col = 0
    
    for i in range(1,len(ladder)):
        current_col = i
        for height in range(1,len(ladder[0])):
            # if moving right available 
            # print(f'current_col, height : {current_col}, {height}')
            if ladder[current_col][height] == 1:
                # move column
                current_col += 1
                
            # if moving left available
            elif ladder[current_col-1][height] == 1:
                current_col -= 1
            
            # else just go downward
            else:
                continue
        if i != current_col:
            return False
        else:
            continue
    return True

N, M, H = list(map(int, sys.stdin.readline().rstrip().split()))

ladder = [[0]*(H+1) for _ in range(N+1)]

# build ladder
for i in range(M):
    a, b = list(map(int, sys.stdin.readline().rstrip().split()))
    
    ladder[b][a] = 1

# full search
# dfs
added_ladder_cnt = 0
ans = int(2e9)

def dfs(ladder,x,y): # x, y -> 이전에 놓은 위치 
    global added_ladder_cnt
    global ans
    
    if ans_ladder(ladder):
        ans = min(ans, added_ladder_cnt)
        return
    
    if added_ladder_cnt >= 3:
        return
    
    for i in range(1, N):
        for j in range(1, H+1):
            if (i,j) <= (x,y):
                continue
            
            if ladder[i][j] == 0 and ladder[i-1][j] == 0:
                ladder[i][j] = 1
                added_ladder_cnt += 1 
                dfs(ladder, i, j)
                added_ladder_cnt -= 1
                ladder[i][j] = 0

dfs(ladder,0,0)

if ans == int(2e9):
    print(-1)
else:
    print(ans)