https://www.acmicpc.net/problem/17070 이 문제는 파이프를 정해진 방식대로 밀어서 끝까지 가는 경로가 몇 개인지 구하는 문제이다. 이 문제에서 파이프는 3가지 상태를 가지고 있다. 가로,세로,대각선이다. 그리고 이 세가지 상태에 따라 다음칸으로 움직일 수 있는 방법이 나뉜다. 가로의 경우에는 가로로 한칸 대각선으로 한칸, 세로의 경우에는 세로로 한칸 대각선으로 한칸, 대각선의 경우에는 가로로,세로로,대각선으로 한칸 움직일 수 있다. 이렇게 움직일 때 꼭 비어있어야 하는 칸들은 아래와 같다.우리는 시작이 있고 끝으로 가는 경우의 수란 점에서 그래프 경로 찾기라는 걸 알게된다. 그렇다면 경로 찾기하면 BFS 아님 DFS인 것을 알 수 있다. 그런데 이 문제의 추가시간이 엄격한걸..