✅사다리 조작 (골드4)

문제 출처 : https://www.acmicpc.net/problem/15684

15684번: 사다리 조작

 

#1. 개선할 점

 

실패 요인

- 사다리가 연속하는 것을 고려하지 않았음 -> 문제 조건 제대로 정리하자.

 

- 2차원 배열로 풀 수 있는 문제였는데 1차원으로 검사하다가 너무 복잡해서 막혔다.

-> 2차원 공간을 다룰 때는 2차원 배열을 생각하자.

 

- 시간부족, 설계하고 검토하는데 너무 오래걸렸다. -> 문제를 익숙해질 때까지 반복해서 풀면서 구현력을 높이자.

 

 

#2. 다시 풀기

 

- depth만큼 모든 경우를 다 구하는 풀이인데

O((300 + 300 * 300 + 300 * 300 * 300 )* 300) 

(사다리 1개 세우는 모든 경우의 수 + 사다리 2개 세우는 모든 경우의 수 + 3개 세우는 모든 경우의 수) * 사다리 타기

이므로 시간 초과가 난다.

 

-> 따라서 백트래킹을 통해 경우의 수를 줄이면서 답을 찾아야 한다!!!!

 

import sys
input = sys.stdin.readline

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

def dfs(repeat, depth, x, y) :
    global ans

    if check() : # 통과했으면 반환
        ans = min(ans, repeat)
        return
    elif repeat == depth : # 3개 설치했으면 이제 그만
        return

    for i in range(x, H+1) :
        for j in range(y, N) :
            if board[i][j] == 0 and board[i][j-1] == 0 and board[i][j+1] == 0 :
                board[i][j] = 1
                if j+2 < N-1 : # 다음에 설치할 수 있는 사다리의 열이 범위 안에 있으면
                    dfs(repeat+1, depth, x, y+2) # 행 변경 x
                else :
                    dfs(repeat+1, depth, x+1, y) # 범위 밖에 있으면 행 변경 o
                board[i][j] = 0

def check() :
    for j in range(1, N+1) :
        now = j
        for i in range(1, H+1) :
            if board[i][now-1] == 1 :
                now -= 1
            elif board[i][now] == 1 :
                now += 1

        if now != j :
            return False
    return True

        
for _ in range(M) :
    a, b = map(int, input().split())
    board[a][b] = 1

res = dfs(0, 3, 0, 0)
if ans == 1e9 :
    print(-1)
else :
    print(ans)

 

- 다섯시간동안 머리 꽁꽁 싸맸던 문제 ........ 그동안 성장했길 빈다..🙏