import sys
input = sys.stdin.readline
N,M,H = map(int,input().split())
graph = [[0]*(N+1) for i in range(H)]
for i in range(M):
a,b = map(int,input().split())
graph[a-1][b] = 1
def ladder(now):
for h in range(H):
if graph[h][now]:
now -= 1
elif graph[h][now+1]:
now += 1
return now
def success():
for n in range(N):
if n != ladder(n):
return False
return True
def DFS(last,cnt):
global result
if cnt >= result:
return
if success():
result = cnt
return
for nh in range(last+1,(N-1)*H):
n = nh%(N-1)+1
h = nh//(N-1)
cant = False
if graph[h][n-1] or graph[h][n] or graph[h][n+1]:
continue
graph[h][n] = 1
DFS(nh,cnt+1)
graph[h][n] = 0
result = 4
DFS(-1,0)
if result == 4:
print(-1)
else:
print(result)
브루트 포스로 해결하였다.
처음에 문제를 대충 읽고 아니 이걸 어떻게 구현하지? 하고 막막했었는데, 맨 마지막에 출력부분에서 "정답이 3보다 큰 값이면 -1을 출력한다." 라는 글자를 보자 "아 그냥 브루트 포스하면 되겠구나" 하게 되었다.
특별할게 없는 알고리즘이다.
1. 현재 cnt값이 지금까지의 최솟값보다 크거나 같으면 return
2. 브루트포스로 모든 좌표에 사다리를 놓아봄 (이때 양 옆이나 현 위치에 사다리가 있으면 안된다)
3. 사다리를 놓을때마다 success 함수를 실행, 성공시 result값 갱신
4. 결과 출력
오늘의 교훈) 입력과 출력을 꼼꼼이 읽어보자