[Python][백준] 15684번 사다리 조작

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

공부 날짜 : 2022.09.10
정답 참조 여부 : O? △?

사다리 타기의 형태가 주어지는데 3번 이하로 다리를 추가해서 입력과 출력이 같게 할수 있나를 판단하는 문제였다.

---

풀이 방법은 조건에 맞춰 3개 이하로 다리를 놓을 수 있는 모든 경우의 수를 따져 보는 것이다.

가능한 모든 방법을 dfs로 구하고 각 사다리 상태에 따라 1번넣었을때 1번이 나오나 따져보는 방법으로 코드를 작성했으나, 수많은 시간초과....

시간을 단축하기 위해 다양한 방법을 시도했으나 도저히 안되서 정답을 참고하였다.

시간초과 코드의 문제는

    #이전 함수에서 추가된 함수의 좌표를 복원
    x = (num%5)
    if x == 0:
        x = 5
    y = (num//5) + 1
    
     
    #현재 깊이에서 안되면 다음 깊이 탐색                
    for i in range(y,h+1):
        for j in range(x,n):
            if data[i][j] == False and data[i][j+1] == False and data[i][j-1] == False:
                data[i][j] = True
                #방금 추가해준 사다리 위치를 기억하고 그다음 사다리부터 추가되도록 작성
                #추가된 좌표를 하나의 값으로 바꿔서 다음 함수로 보냄
                dfs(depth+1,data, ((y-1)*5 + x)+2)
                data[i][j] = False

이런 식으로 다음 함수를 호출할때 추가한 사다리의 좌표를 하나의 값으로 바꿔줘서 보내준뒤 다음 함수에서 복원하는 과정을 거쳤다.

하지만 복원의 연산이 간단하다 하더라도 재귀하는 과정이 워낙 많다보니 시간이 쌓여서 시간초과를 발생시킨 것이다.

정답을 참조한 결과 x,y를 그냥 바로 넘겨주고 세로선이 바뀌면 가로선을 0으로 만들어 주는 식으로 코드를 작성했고 이 부분만 바꿔주니 정답으로 나왔다.

코드의 알고리즘이 참고했던 정답과 방법이 아예같았고 사다리 좌표를 넘겨주는 방법의 차이만 있었기 때문에 조금만 더 생각해봤으면 정답을 안보고 풀었을거라는 아쉬움이 남는다.

소스코드

import sys
input = sys.stdin.readline

n, m, h = map(int, input().split())

data = [[False]*(n+1) for _ in range(h+1)]


#데이터 입력받기
for _ in range(m):
    x,y = map(int,input().split())
    data[x][y] = True
    
    

#현재 그래프 상태에서 조건을 만족하는지 판단.    
def check(data):
    for i in range(1,n):
        my_num = i
        for j in range(1,h+1):
            #내려가던중 오른쪽으로 선있으면 숫자 +1
            if data[j][my_num]:
                my_num += 1
            #내려가던중 왼쪽에 선있으면 숫자 -1
            elif data[j][my_num-1]:
                my_num -= 1
            
        if my_num != i:
            return False
        
    return True

result = 4
#전체 탐색을 위한 재귀 함수
def dfs(depth, data, x,y):
    global result
    if depth >= result:
        return
    
    #주어진 사다리가 조건을 충족하면 결과 갱신
    if check(data):
        result = min(result, depth)
        return
    
    if depth == 3:
        return
  
    #현재 깊이에서 안되면 다음 깊이 탐색                
    for i in range(x,h+1):
        ########################
        if x == i:
            k = y
        else:
            k = 0
        ########################
        for j in range(k,n):
            if data[i][j] == False and data[i][j+1] == False and data[i][j-1] == False:
                data[i][j] = True
                #방금 추가해준 사다리 위치를 기억하고 그다음 사다리부터 추가되도록 작성
                #추가된 좌표를 하나의 값으로 바꿔서 다다음 함수로 보냄
                dfs(depth+1,data, i ,j+2)
                data[i][j] = False
                    
    
dfs(0,data,1,1)
if result == 4:
    result = -1
    
print(result)