[BOJ15684] 사다리 조작

i번 세로선 결과가 i번이 나오기 위해 추가해야되는 최소 가로선 개수

• 사다리는 N개의 세로선, M개의 가로선으로 구성
• 가로선 놓을 수 있는 위치 H개
• 가로선 연속 X

입력

• N(2<= <=10), M(0<= <=(N-1)*H), H(1<= <=30)
• 둘째 줄부터 M개의 줄에 가로선 정보 (a, b) (1<= <=H) (1<= <=N-1)
• 왼쪽, 상단부터 1 시작, 가로선 연속 X

출력

• i번 세로선의 결과가 i번이 나오기 위해 추가해야되는 최소 가로선 개수
• 답이 3보다 크면 -1, 불가능한 경우도 -1

설계

• 사다리를 그래프로 구현 (2중 배열이용)
• 각 위치의 가로선 긋는 백트래킹 구현
  • 백트래킹 끝나는 조건 : 가로선 개수 (가로선은 0~3까지 반복문)
  • 세로선 시작 끝이 같으면 break 후 출력, 없으면 -1 출력
• 사다리 타는 로직
  • 현재 위치 (y, x)에서 체크해야될 양쪽 가로선 (y-1, x), (y, x)
  • y-1 은 왼쪽으로 옮겨감 -> (y-1, x+1)
  • y 는 오른쪽으로 옮겨감 -> (y+1, x+1)
  • 가로선이 없는 경우 (y, x+1)

피드백

• 백준에서 n과 m 백트래킹 시리즈를 모두 풀었음에도, 단순 파라미터 문제로 계속 헤맴
• 시간초과가 계속 나서, 순열로 작성한 코드를 조합으로 변경
• 즉, 가능한 가로선을 방문하는 과정에서 2중 for문(n, h)이 쓰이는데, n 반복 과정에서 이전 값을 기억해 다시 사용
• 이 과정에서, dfs의 파라미터로 i+1을 (i : n반복 인덱스) 넣었는데, 이번엔 답이 틀렸다고 떴음 (테스트 케이스는 다 맞았음)
• 파라미터로 그냥 i를 넣으니 통과
• 왜 i+1은 안 되는지 진짜진짜 모르겠음… 이게 시간 절약에 더 맞는 거 같은데…

How I solved(click to github)

---

ref :
BOJ15684