백준 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)
Author And Source
이 문제에 관하여(백준 15684 사다리조작), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@wook2pp/백준-15684-사다리조작저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)