[Python/백준] 15684번 - 사다리 조작

문제

백준 15684번 - 사다리 조작

해결 과정

1. 우선 입력받은 값에 따라 사다리 만들기
2. 가로선을 만드는 DFS 함수

• cnt는 가로선의 개수
• 단, 두 가로선이 연속하거나 서로 접하면 안 된다
• 현재 위치가 (i, j)이고, 사다리가 연결되어 있지 않다면(0), 현재 위치 (i, j)에 가로줄을 하나 만들고 j+2로 점프하여 재귀 함수를 호출한다.

3. i번 세로선의 결과가 i번이 나오는지 확인하는 check함수

• 1번부터 n까지 확인해야 함
• 현재 위치 (i,j)에 사다리가 연결되어 있으면(1) 오른쪽(i,j+1)으로 이동
  연결되어 있지 않고(0) 왼쪽(i,j-1)이 연결되어 있는지(1)이 확인하고 맞으면 왼쪽(i,j-1)으로 이동
• 현재 위치에서 사다리 한칸 내려가서 (i+1,j) 위의 과정을 다시 반복

시행착오

• 사다리를 어떻게 만들지도 모르겠는데? -> 행은 가로줄 h, 열은 세로줄 n인 2차원 배열, A번 세로줄과 A+1번 세로줄의 사이에 B번 가로줄로 연결한다면, 사다리 [A][B]를 연결(1)한다.

풀이 (Pypy3 제출)

import sys

n,m,h = map(int,sys.stdin.readline().split())

# 2차원 배열로 사다리 만들기
ladder = [[0] * n for _ in range(h)]

for _ in range(m):
  a,b = map(int,sys.stdin.readline().split())
  ladder[a-1][b-1] = 1

# i번 세로선의 결과가 i번이 나오는지 확인하는 check 함수
def check():
  for i in range(n):
    tmp = i
    for j in range(h):
      if ladder[j][tmp] == 1:
        tmp += 1
      elif tmp > 0 and ladder[j][tmp-1] == 1:
        tmp -= 1
    if tmp != i:
      return False
  return True

# 사다리 만드는 DFS 함수
def dfs(cnt, x, y):
    global ans
    if ans <= cnt:
        return
    if check():
        ans = min(ans, cnt)
        return
    if cnt == 3:
        return
    for i in range(x, h):
        if i == x:
          tmp = y 
        else:
          tmp = 0
        for j in range(tmp, n - 1):
            if ladder[i][j]:
                j += 1
            else:
                ladder[i][j] = 1
                dfs(cnt + 1, i, j + 2)
                ladder[i][j] = 0

ans = 4
dfs(0, 0, 0)
print(ans if ans < 4 else -1)