A. 문제설명
https://www.acmicpc.net/problem/15684
문제에 대한 자세한 설명은 링크 참조
1. N개의 세로선과 M개의 가로선이 주어짐
2. 각 세로선에는 H개의 가로선을 놓을 수 있는데, 이는 좌표의 Y축 좌표에 해당된다고 이해하면 된다.
3. 주어진 가로선 이외에 가로선을 전체에서 추가로 3개까지 사용하여, i번째 사다리의 출발점이 i번째 도착점에 도달하도록 사다리를 조작
4. 조작에 추가 가로선이 3개 넘게 필요하다면 -1 반환, 그 이하면 그 갯수 반환
B. 접근법
DFS + 시뮬레이션
1. DFS: 0~3개까지 가로선 놓는 조합 구하기에 사용. 가로선을 추가로 놓는 조합에 대해서는 완전 탐색이 필요하고 해당 조합을 만드는 건 DFS를 사용하자.
2. 시뮬레이션: 가로선을 놓고나서 사다리 시뮬레이션을 돌리기 위한 문제 조건에 충실한 구현
C. 풀이
1. 먼저 가로 N, 세로 H 크기의 사다리 배열에서 각 모든 위치에서 DFS 탐사를 시작한다.
2. 각 위치에서 호출된 DFS 함수는 아래와 같이 동작한다.
2-1. 3-depth까지 인자로 넘겨진 좌표를 visit 배열에 체크하며 마킹된 해당 사다리판에서 시뮬레이션을 한번 수행한다.
2-2. 그 다음 만약 3-depth에 도달하지 못했다면, 재귀호출로 depth를 하나 더 깊이 들어가고, 좌표는 그 다음으로(우하향) 탐사한다.
2-3. 그렇게 되면, DFS 함수가 하나의 좌표에서 불리어질 때마다, 가로선 1개 추가, 2개 추가, 3개 추가... 까지 되어가며 시뮬레이션을 수행할 수 있다.
3. 각 시뮬레이션을 수행될 때마다 출발점에서 도착점의 세로선 위치가 모두 동일할 때만 통과로 간주한다.
4. 그렇게 시뮬레이션을 통과하는 조합 중 가장 적은 수의 추가 가로선 수를 반환한다.
D. 내 코드
