[BOJ - 17070] 파이프 옮기기 1

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

17070번: 파이프 옮기기 1

DP,DFS,BFS 그 어떤것으로 해도 C/C++일때 배열의 크기가 작아서 AC할 수 있을것같다.

근데 DFS로 짜면 시간이 많이 걸릴것같고, BFS는 짜기 번거로울것 같아서 그냥 DP로했다.

DP 배열을 3x16x16으로 하여, 눕는 파이프, 선 파이프, 대각선 파이프 에 대해 분할해서

다음점에 대해 이전점의 Memoization 값들을 활용하여 갱신해주는 방법으로 DP풀이를 하였다.

아마 코드를 보면 어떠한 방식으로 했는지 짐작이 갈것이다.

하지만 여기서도 함정이랄게 한가지 있는것이 바로 못가게 막아놓은 1이라는 포인트인데

누운것, 선것은 직선형에 차지하는 칸이 두개기 때문에 한가지 조건으로 전부 거를수 있지만

대각선은 4가지 영역을 차지하기 때문에 걸러줄수 있는 조건이 한가지 필요하다.

다음 점에 대해 계산할때 그점이 영역을 차지할수 있는지 없는지를 판별하여 계산하는 조건을 추가하여

AC를 받았다.