[백준] 17070_파이프 옮기기1 (DFS & DP 이용)

📕 문제

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

17070번: 파이프 옮기기 1

 

💡 풀이법

1. dfs와 dp를 이용했다. 하지만 파이프가 놓인 방향에 따라 경로가 달라지기 때문에 총 3차행렬을 만들어서 각 matrix칸마다 길이가 3인 리스트가 들어가도록 했다.

2. 파이프가 놓여진 방향에 따라 갈수 있는 방향이 다르기때문에 방향 리스트도 각각 다르게 만들었다.

3. 방향에 따라 갈수 있는 방향을 for문을 돌며 확인한다.

4. 대각선일때는 방향의 위와 왼쪽도 봐줘야 하기 때문에 따로 if문을 만들어줬다.

5. 다음 위체에 대해서 실행한 dfs의 반환값을 현재 위치에 담아준다.

6. dfs를 돌면서 도착지에 도착했다면 1을 리턴하고 아직 dp가 -1이라면 한번도 방문하지 않은 위치이기 때문에 , 그 위치에 대해서 다시 탐색을 해준다.

7. 위의 두 경우가 아니라면 이미 dp가 채워져있는 곳이기 때문에 dp의 값을 반환한다.

8. 모두 다 돌고 나면 dp에는 각 위치에서 도착지까지 갈수 있는 경로의 가짓수가 담기게 된다.

9. dp의 시작점 위치의 값을 출력하면 된다.

 

dxy = [[(0,1),(1,1)],[(1,0),(1,1)],[(0,1),(1,0),(1,1)]]
# 가로:0, 세로:1, 대각선:2

def dfs(x,y,d):
    if x == y == N-1:
        return 1

    if dp[x][y][d] == -1:
        dp[x][y][d] = 0
        for dx, dy in dxy[d]:
            nx, ny = x + dx, y + dy
            nd = dx*(dy+1)

            if -1 < nx < N and -1 < ny < N and not matrix[nx][ny]:
                if nd == 2 and (matrix[nx-1][ny] or matrix[nx][ny-1]):
                    continue
                dp[x][y][d] += dfs(nx, ny, nd)
    
    return dp[x][y][d]

N = int(input())
matrix = [list(map(int, input().split())) for _ in range(N)]
dp = [[[-1]*3 for _ in range(N)] for _ in range(N)]
dfs(0,1,0)
print(dp[0][1][0])