15684번 – 사다리조작

문제

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

풀이

코드

n, m, h = map(int, input().split())
arr = [list(map(int, input().split())) for _ in range(m)]
board = [[0]*n for _ in range(h)]
for y, x in arr: board[y-1][x-1] = 1

def run():
  for i in range(n):
    y, x = (0, i)
    while(y != h):
      if board[y][x] == 1: x = x+1 # 오른쪽     
      elif(x > 0 and board[y][x-1] == 1): x = x-1 # 왼쪽
      y = y+1
    if x != i: return False
  return True

def DFS(startY, depth, maxDepth):
  if depth == maxDepth:
    if run():
      print(depth)
      exit(0)
    return
  for y in range(startY, h):
    for x in range(n-1): # 마지막줄 추가 노
      if board[y][x] == 1: continue
      if board[y][x-1] == 1: continue
      if board[y][x+1] == 1: continue
      board[y][x] = 1
      DFS(y, depth+1, maxDepth)
      board[y][x] = 0

def answer():
  maxDepths = [0, 1, 2, 3]
  for md in maxDepths: DFS(0, 0, md)
  print(-1)
  
answer()