[백준] 골5 - 파이프 옮기기 1

17070번: 파이프 옮기기 1

문제 설명

파이프가 (0,0), (0,1)에 위치한다. 다음 그림과 같은 모양으로 파이프를 옮길 수 있을 때 (n, n)까지 파이프를 옮기는 경우의 수를 구하는 문제이다.

다만 위 그림은 옮기는 구간에 벽이 없는 경우에만 가능한 경우다. 옮기는 범위에 벽이 있는 경우 그 방향으로 파이프를 옮길 수 없다.

풀이

Dynamic Programming Top-Down 방식으로 문제를 해결했다. DFS함수는 매개변수로

(direction y, direction x, end y, end x)

를 가지고 있고 줄여서 (dy, dx, ey, ex)라 칭한다.

dy, dx는 총 3가지 경우가 있는데

1. 0, -1이면 가로
2. -1, 0이면 세로
3. -1, -1이면 대각선

방향으로 파이프가 ey, ex를 끝으로 나열되어 있다는 것이다.

return은 매개변수와 같은 파이프 상태가 나올 수 있는 모든 경우의 수의 합을 리턴한다.

DFS(0, -1, n, n) + DFS(-1, 0, n, n) + DFS(-1, -1, n, n)

를 구하면 문제의 정답을 얻을 수 있게 설계했다. (Top-Down 이므로)

코드