[백준] 15684 사다리 조작

---

사다리 게임에 주어진 사다리에 가로선을 추가하여 i번째 사다리 게임의 결과가 i가 나오도록 하는 문제이다.

 

문제 자체는 백트래킹 알고리즘으로 간단히 해결할 수 있다. 하지만 시간, 메모리 제한을 고려하여 최적화 해야한다.

 

사다리를 배열로 치환하고 (r, c)에 사다리가 있을 경우 1 또는 True, 없을 경우 0 또는 False로 표시한다. 그리고 사다리를 놓으며 따라 내려간다. 만약 i가 (i, c)에서 사다리를 만날 경우 i = i + 1, (i-1, c)에서 만날경우 i = i - 1을 수행한다.

 

반복마다 사다리를 타고 내려가 임의의 i에 대해서 결과가 i가 나오는지 확인한다.