BOJ_15684_사다리조작

백준 #15684 사다리 조작

• 알고리즘 스터디 문제 풀이입니다.
• 백준 15684번 에서 풀어볼 수 있습니다.

문제설명

사다리의 형태가 세로, 가로 크기와 세로축 사이에 서로 연결된 사다리의 전체 정보가 주어진다. 이 때, 사다리의 세로축을 추가적으로 서로 연결하여 사다리타기 게임을 진행했을 때 i번째 에서 출발한 사다리타기의 결과가 i번이 나오도록 하는 추가적인 가로선 개수의 최솟값을 구하는 것이 문제이다.

풀이

먼저, 해당 문제의 풀이법은 브루트포스(백트래킹)으로 접근했다. 주어진 N과 M, 그리고 H의 크기가 각각 210, 130, 0~270 으로 작았기에 모든 경우를 세보아도 시간복잡도상 문제가 없을 것이라고 판단했기 때문이다.

따라서 경우에 따라 사다리를 생성하는 메서드인 make_ladder와 이렇게 만들어진 사다리를 타서 결과를 확인하는 go_down_ladder를 구현해 풀이해주었다. 전체적인 로직은 다음과 같다.

1. 가로축보다 1칸을 추가적으로 더 만들어 해당 칸을 종료칸으로 가정한다.
2. make_ladder 메서드로 사다리 가로선을 1개부터 3개까지 차례대로 추가해가며 확인을 한다.(3개가 넘어갈 시 -1을 리턴하기 때문에 3까지만 확인해준다.)
3. make_ladder로 dfs 백트래킹을 해주고, 시간복잡도를 줄이기 위해 이전에 확인한 조합은 다시 확인하지 않도록 해준다.
4. make_ladder의 종료조건(추가선을 주어진 개수만큼 사용해 만든 경우)에서 go_down_ladder를 통해 i번째 시작점이 i번째 도착점으로 결과를 내는지 확인해주어 만약 맞다면 해당 추가선의 개수를 리턴해준다.
5. 만약 아니라면 2번으로 돌아가 가로선을 1 추가해주어 다시 진행해준다.