백준 - 17070번(파이프 옮기기 1) / C++
DFS로 풀게되면 시간초과의 우려가 있어 DP로 풀었다. 현재칸을 ( i, j )라고 했을 때, ( i, j-1 ) 의 칸에서 이어지는 경우, ( i-1, j ) 의 칸에서 이어지는 경우, ( i-1, j-1 ) 의 칸에서 이어지는 경우 3가지의 경우로 파이프가 이어질 수 있다. 3차원배열을 선언하여 각 칸에 들어오는 파이프의 개수가 가로에서 들어왔는지, 세로에서 들어왔는지, 대각선에서 들어왔는지 개수를 세주었다. index => 가로 : 0 대각선 : 1 세로 : 2 각 그림에서 주황색 칸은 값을 채우려는 현재 위치이고 빨간색 화살표는 파이프가 이어지는 방향, 파란색 화살표는 이으려는 파이프의 이전 파이프의 방향이다. 1. ( i, j-1 ) 칸의 경우 가로로 이어지는 경우 dp[0][i][j] = d..