백준 15684 사다리조작

dfs, 백트래킹을 이용하는 브루트포스 문제였다.

사다리지점을 어떻게 탐색하느냐는 문제와 주어진 그래프에서 사다리조작이 이루어 졌는지 확인하는 문제이다.

사다리 지점을 재귀로 탐색해야 하는데 지점을 탐색하는 과정에서 처음 0,0부터 탐색하다보니 재귀의 과정에서 필요없는 탐색이 너무 많이 이루어져서 시간초과가 났다.

시간초과가 난 코드

import copy
n,m,h = list(map(int,input().split()))
graph = [[0 for i in range(n)] for i in range(h)]
for i in range(m):
    a,b = list(map(int,input().split()))
    graph[a-1][b-1] = 1

def check():
    for i in range(n): ## n번줄까지
        start = i
        for j in range(h):
            if graph[j][start]: ## 사다리 시작점를 만났다면
                start += 1
            elif start > 0 and graph[j][start-1]: ## 왼쪽에 사다리가 있다면
                start -= 1
        if i != start:
            return False
    return True

def solve(cnt):
    global answer
    if check():
        answer = min(answer,cnt)
        return
    elif cnt == 3 or answer <= cnt:
        return
    for i in range(h):
        for j in range(n):
            if graph[i][j]:
                continue
            elif j > 0 and graph[i][j-1]:
                continue
            elif j > 0 and not graph[i][j-1]:
                graph[i][j-1] = 1
                solve(cnt+1)
                graph[i][j-1] = 0
answer = 4

solve(0)
if answer >= 4:
    answer = -1
print(answer)

그렇기 때문에 가로선에서 먼저 찾아보고 없다면 다음 세로선으로 넘어가 보는 방법이 더 빠르게 탐색하는 방법이었다.

import copy
n,m,h = list(map(int,input().split()))
graph = [[0 for i in range(n)] for i in range(h)]
for i in range(m):
    a,b = list(map(int,input().split()))
    graph[a-1][b-1] = 1

def check():
    for i in range(n): ## n번줄까지
        start = i
        for j in range(h):
            if graph[j][start]: ## 사다리 시작점를 만났다면
                start += 1
            elif start > 0 and graph[j][start-1]: ## 왼쪽에 사다리가 있다면
                start -= 1
        if i != start:
            return False
    return True

def solve(cnt,x,y):
    global answer
    if check():
        answer = min(answer,cnt)
        return
    elif cnt == 3 or answer <= cnt:
        return
    for i in range(x,h):
        if i == x: ## 같은 가로선에서 더 추가할 수 있는지 먼저 확인
            k = y
        else:
            k = 0
        for j in range(k,n):
            if graph[i][j]:
                continue
            elif j > 0 and graph[i][j-1]:
                continue
            elif j > 0 and not graph[i][j-1]:
                graph[i][j-1] = 1
                solve(cnt+1,i,j+1)
                graph[i][j-1] = 0
answer = 4

solve(0,0,0)
if answer >= 4:
    answer = -1
print(answer)