[백준][python]15684 사다리 조작

문제

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

소스코드

import sys
input = sys.stdin.readline

if __name__ == "__main__":
    #시작점이 사다리를 타고 도착점에 도달했을 때 시작점과 동일한지 체크
    def chk():
        for i in range(1,n+1): #세로선 하나씩 체크
            idx = i
            for j in range(1,h+1): #가로선 체크
                if graph[j][idx]: #idx ~ idx+1 사이에 가로선이 있음 idx는 idx+1이 되고 idx+1은 idx가 됨
                    idx +=1
                elif graph[j][idx-1]:#idx-1 ~ idx 사이에 가로선이 있음 idx는 idx-1이 되고 idx-1은 idx가 됨
                    idx -=1
            if not idx == i: # 가로선 다 체크 후 끝지점에 왔을 때 시작과 동일한지 체크
                return False
        return True


    def dfs(cnt,x):
        global answer
        if cnt > 3: #가로선 갯수가 3개가 넘어가면 종료
            return
        if chk(): #사다리를 타고 시작노드가 종료 노드랑 같아지는지 체크
            if answer > 0: # 이미 성공했다면 더 작은 갯수로 변경
                answer = min(cnt,answer)
            else: #최초 성공인 경우 갯수 초기화
                answer = cnt
            return
        # 연속되지 않는 가로선 그리기
        for i in range(x,h+1): # x 한번 체크한 가로선 다음부터 체크(시간초과방지)
            for j in range(1,n):
                if not graph[i][j]: #가로선이 현재 없고
                    if j-1 >= 0 and graph[i][j-1]: #왼쪽에 연속된 가로선 없고
                        continue
                    if j+1 < n and graph[i][j+1]: #오른쪽에 연속된 가로선 없고
                        continue
                    graph[i][j] = 1
                    dfs(cnt+1,i)
                    graph[i][j] = 0 #백트래킹으로 가로선 취소

    n,m,h = map(int,input().split())
    graph = [[0] * (n + 1) for _ in range(h + 1)]

    if not m: #입력되는 가로선이 없으면 바로 종료
        print(0)
        sys.exit()

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

    answer = -1

    dfs(0,1)

    print(answer)

설명

사다리를 놓을 수 있는 위치를 백트래킹으로 체크한다

(1,2) 라고 가로선이 주어진다면 1은 행이고 2는 열이라서 2~3을 잇는 가로선이라고 생각해준다

가로선을 체크해줄 때 왼쪽과 오른쪽에 이어지는 가로선이 없는지 체크해주면서 dfs를 실행한다

후기

• dfs로 재귀를 탈 때엔 이전에 어디까지 탐색했는지 체크 후 그 값을 파라미터로 넘겨서 그 다음부터 재귀가 탐색하도록해야 시간초과가 발생하지 않는다
• 시작노드와 끝노드를 체크하는 방식을 수정해서 시간초과 오류를 수정했다
• answer가 min인 경우를 체크하지 않아서 좀 헤맸는데 min으로 표시하면 -1을 어떻게 해야할지 헤맸다;; 임시방편으로 저렇게 했는데 더 좋은 방법을 찾아봐야겠다