백준 17070. 파이프 옮기기 1

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

17070번: 파이프 옮기기 1

 

순열을 구하듯이 dfs로 모든 경우를 탐색하는 문제였다. 

모든 경우 탐색을 위해 파이프의 현재 방향에 따라 다음 방향으로 이동할수 있는지 확인하고, 이동할수 있으면 이동시키면 된다.

모든 dfs로 모든 경우를 구하는 문제들이 그렇듯 다음 과정을 거쳐야 한다.

 

1. 이동 전 상태를 저장해놓는다.

2. 이동한지 확인하고 가능하면 이동한다.

3. 이동하고 다시 현 상태로 되돌아온 후 (현재 재귀로) 에는 이전 저장한 상태로 되돌아간다.

 

 

 

 

---

 

dp 풀이

푼 후에 다른 분들 풀이를 보니 dp 로 푸는 방법도 있었다.

 

d[dir][r][c] : [r][c]에 dir 방향으로 도착할수 있는 경우의 수 

 

위 풀이에서도 그랬지만 파이프는 오른쪽, 아래 방향으로만 움직일수 있기 때문에 최초에 [1][1]에 존재하는 파이프의 왼쪽 부분은 사실 신경쓸 필요가 없다. 

 

d[가로][r][c] : 가로 방향으로 [r][c]에 도착한다는 것은 이전에 파이프의 방향은 가로 혹은 대각선 방향이었음을 의미한다. 

d[세로][r][c] : 세로 방향으로 [r][c]에 도착한다는 것은 이전에 파이프의 방향은 세로 혹은 대각선 방향이었음을 의미한다.

d[대각선][r][c] : 대각선 방향으로 [r][c]에 도착한다는 것은 이전에 파이프의 방향은 가로 혹은 세로 혹은 대각선 방향이었음을 의미한다.

 

가로, 세로 방향은 현재 칸 r,c만 벽이 아니면 되지만,

대각선 방향으로 [r][c]에 도달하는 경우를 계산할때는 [r-1][c], [r][c], [r][c-1] 모두 벽이 아닌지 확인을 해줘야 한다.