백준 3109. 빵집

https://www.acmicpc.net/problem/3109

3109번: 빵집

 

파이프는 오른쪽, 오른쪽 위 대각선, 오른쪽 아래 대각선으로 설치할수 있다. 

 

dfs로 첫 열의 각 행을 탐색해주면 되는데 오른쪽, 오른쪽 위 대각선, 오른쪽 아래 대각선 순으로 설치해보면서 마지막 열에 도달할수 있는지 확인하면 된다. 

 

이 문제의 핵심은, 보통 dfs 탐색을 할때는 쭉 가다가 막히는 경우가 있으면 return 으로 되돌아오고 보드(혹은 맵)의 상태를 원상태로 되돌려줘야 한다. (이 루트는 틀렸기 때문) 

하지만 이 문제는 이렇게 할 경우 시간초과가 난다. 

 

생각해보면 어처피 파이프는 오른쪽, 오른쪽 위 대각선, 오른쪽 아래 대각선으로 밖에 설치할수 없다. 즉 오른쪽으로 밖에 진행이 안된다.

따라서 dfs로 한 곳을 뚫다가 막히는 경로가 있다면 그 경로는 다른 행을 출발점으로 하는 dfs 에서도 당연히 막히는 경로기 때문에 탐색해볼 필요가 없다.

 

따라서 이 문제는 평범한 dfs 문제지만 막히는 경로를 되돌려 주지만 않으면 된다.