[백준 15684] 사다리 조작

문제 보기

이 문제는 브루트 포스 문제이다.

완전탐색을 위해서 DFS를 재귀적으로 구현하였다.

문제를 풀기위한 로직은 다음과 같다.

1. 사다리를 놓을 수 있는 경우의 수 0, 1, 2, 3에 대하여, 그 갯수만큼 사다리를 놓을 때의 모든 경우의 수를 순서대로 탐색한다. (44~46번째 줄)
2. 만약 answer의 값이 변경되었다면(= sys.maxsize가 아닐 때), 필요한 사다리의 갯수를 찾았다고 간주하고 정답을 출력한다. (47~51번째 줄)
3. 사다리를 놓을 수 있는 모든 위치를 탐색하면서, 사다리를 놓을 모든 경우의 수를 DFS로 탐색한다. (32~41번째 줄)
4. DFS를 재귀적으로 실행하면서 정해놓은 갯수만큼 사다리를 놓았다면, 사다리 게임을 시작하고, i번째 사다리에서 시작해서 i번째 사다리에서 모두 끝나는지 검사한다. 만약 모든 사다리가 조건을 만족한다면 정답을 찾은 것이므로 해당 게임에서 놓은 사다리의 갯수가 정답이므로 answer값을 변경한다. (11~30번째 줄)

처음에 문제를 풀었을 때 6000ms의 시간으로 통과했다.

원인을 찾는데 오랜 시간이 걸렸지만, 39번째 줄에서 r과 c의 매개변수를 i와 j로 넘겨주어야 했지만, 실수로 r과 c를 그대로 넘겨주었다.

사다리 게임에서 현재 위치에서 위로는 올라갈 일이 없기 때문에, 재귀적으로 탐색을 진행할 때 현재 위치(i, j)부터 진행하면 되지만, 재귀적으로 탐색을 하는데 원점인 (r, c)부터 탐색을 진행했기 때문에 매우 긴 시간이 걸렸다..

아주 간단한 부분을 놓치고 있었다. 디버깅을 습관화 해야겠다.

import sys
n, m, h = map(int, sys.stdin.readline().split())
board = [[0 for c in range(n + 1)] for r in range(h + 1)]
for i in range(m):
    r, c = map(int, sys.stdin.readline().split())
    board[r][c] = 1
 
 
def solution(r, c, count):
    # termination condition
    if count == ladder:
        result = True
        for j in range(1, n + 1, 1):
            cur_col = j
            for i in range(1, h + 1, 1):
                if board[i][cur_col]:
                    cur_col += 1
                elif board[i][cur_col - 1]:
                    cur_col -= 1
            
            # current line starts and ends at the end of the same line
            if cur_col != j:
                result = False
                break
        
        # if current game is valid, finish recursion
        if result:
            global answer
            answer = count
        return
    
    # Brute Force
    for i in range(r, h + 1, 1):
        for j in range(1, n, 1):
            if not board[i][j - 1] + board[i][j] + board[i][j + 1]:
                # place a ladder
                board[i][j] = 1
                # recursion
                solution(i, j, count + 1)
                # set to initial state
                board[i][j] = 0
 
 
answer = sys.maxsize
for ladder in range(4):
    solution(1, 1, 0)
    # if found the minimum number of ladders
    if answer != sys.maxsize:
        break
# if answer is not in valid range, return -1
print(answer if answer <= 3 else -1)