사다리 조작
https://www.acmicpc.net/problem/14499
삼성 기출문제이다. DFS 문제이다.
어려웠다. 해설을 보고 이해를 했지만, 직집 해결해보기 위해 며칠 동안 붙잡고 있던 문제이다.
풀이
- 사다리를 어떻게 코드로 표현해야 하는지 파악한다.
- 사디리는 어디에 둘 수 있는지 파악한다.
- 탐색을 어떻게 진행할지 생각한다.
사다리를 코드로 표현하는 방법은 다음 그림과 같이 이차원 배열을 이용한다. 사다리를 1과 2로 표현한다.
사다리를 둘 수 있는 곳의 조건은 다음과 같다.
- i행의 j번째의 값과 j+1번째의 값이 0 : 연속되지 않고, 사다리를 둘 수 있는 빈 칸 이라는 의미
- j+1<=n : 동일한 행에 사다리를 둘 수 있다는 의미
탐색은 DFS로 진행한다. 사다리는 최대 3개 까지 둘 수 있다.
사다리를 최대 0개 둘 수 있는 경우, 최대 1개 둘수 있는 경우, 최대 2개 둘수 있는 경우, 최대 3개 둘수 있는 경우로 나눈다.
각 경우에서 DFS를 시작한다. 설명을 위해 빈 칸을 A, B, C.. 로 표현하였다.
