[백준 15684번] 사다리 조작 (Python3)

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. 결과 출력

 

 

오늘의 교훈) 입력과 출력을 꼼꼼이 읽어보자