[백준 / BOJ] 17070 파이프 옮기기 1

문제

출처 : www.acmicpc.net/problem/17070

17070번: 파이프 옮기기 1

새 집으로 이사한 유현이는, 파이프를 옮길려한다. 파이프는 대각선, 왼쪽, 아래로 움직일수있다. 이때, 새 집에 새로운 벽지를 발랐기 때문에, 파이프가 벽을 긁으면 안 된다. 파이프를 N,N 위치로 옮기는 모든 경우의수를 구하는 문제다.

 

풀이

다이나믹 프로그래밍으로 푼 문제다.

문제에서 이동하는 모양을 보면, 항상 최소경로로 이동하기때문에, 최소경로로 이동했는지 고려해주지않고 계산해도 된다. (파이프를 위쪽으로 미는 경우가 없음)

 

이동하는 경우는 크게 3가지인데,

전 위치에서 가로모양으로 도착하는 경우 : (y, x-1)위치에 대각선으로 도착한 경우 + (y, x-1)위치에 가로모양으로 도착한경우

- 세로모양으로 도착한 경우는 가로모양으로 한번에 바뀌지못한다

전 위치에서 대각선모양으로 도착하는 경우 : (y-1,x-1)위치에 대각선, 세로, 가로로 도착하는경우의 합

- 대각선은 세로, 가로, 대각선 전부 한번에 바뀔수있다

전 위치에서 세로모양으로 도착하는 경우 : (y-1,x)위치에 대각선으로 도착한경우 + (y-1,x)위치에 세로 모양으로 도착한경우

- 가로모양으로 도착하는 경우와 같은 이유인데, 전 위치에 가로 모양으로 도착했을경우 한번에 세로모양으로 바뀔수없다

 

위 3가지 경우를 봐주기위해 dp테이블을 3개만들어서 저장해줬고, (가로 도착, 세로 도착, 대각선 도착)

마지막 N,N위치에 도착한 3가지 모양을 전부 합해주면 답이 나온다.

 

주의할 점이 파이프를 이동할때 벽이 있는경우인데, 세로와 가로는 각각 이동시킬 위치에 벽이있으면 이동시키지 못하고, 대각선은 이동시킬 위치와, x-1위치 y-1위치중 한곳에 벽이있으면 이동시키지못한다.

 

소스코드

https://github.com/devxb/JJUNalgo/blob/master/17070%20%ED%8C%8C%EC%9D%B4%ED%94%84%20%EC%98%AE%EA%B8%B0%EA%B8%B0%201/main.cpp

devxb/JJUNalgo