[백준] 17070 파이프 옮기기1 -> dfs로 풀기 vs DP로 풀기

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

17070번: 파이프 옮기기 1

맨처음 떠올랐던건 직관적인 DFS 이다 

dfs로 갈수 있는 방향으로 한칸씩 이동하면서 마지막에 array[n-1][n-1]에 도달하면, (0,0) ~ (n-1,n-1)까지 가는 방법 으로 하나씩 카운트 했다. 

주의할점은 dfs로 갈수있는 칸 체크할 때 가로방향이면  x가 범위안에 있는지,

x < n-1

세로 방향이면 y가 범위안에 있는지 확인해주어야 한다. 

y < n-1

 

대각선 방향이면 x, y 범위 둘다 확인해주어야 한다.

if x < n-1 and y < n-1:

 

 

# 17070 파이프 옮기기

n = int(input())
array = []
for _ in range(n):
    array.append(list(map(int, input().split())))
result = 0  # 방법의 수

def dfs(x, y, dir):
    global result
    if x == n - 1 and y == n - 1: # or 이 아니라 and !! 가 맞다 ;;
        result += 1

    if dir == 0: # 가로
        if y < n-1 and array[x][y+1] == 0:
            dfs(x, y+1, 0) # -> 방향

        if x < n-1 and y < n-1:
            if array[x][y+1] == 0 and array[x+1][y+1] == 0 and array[x+1][y] == 0:
                dfs(x+1, y+1, 2) # \ 방향

    elif dir == 1: # 세로
        if x < n-1 and array[x+1][y] == 0: # 세로
            dfs(x+1, y, 1)

        if x < n-1 and y < n-1:
            if array[x][y+1] == 0 and array[x+1][y+1] == 0 and array[x+1][y] == 0: # 대각선
                dfs(x+1, y+1, 2)

    elif dir == 2: # 대각선
        if y < n-1 and array[x][y+1] == 0:
            dfs(x, y+1, 0) # 가로

        if x < n-1 and array[x+1][y] == 0: # 세로
            dfs(x+1, y, 1)

        if x < n-1 and y < n-1:
            if array[x][y + 1] == 0 and array[x + 1][y + 1] == 0 and array[x + 1][y] == 0:
                dfs(x + 1, y + 1, 2)


dfs(0,1,0)
print(result)

근데 이 문제 유형이 DP로 분류되어있었는데 DP로 푸는건 좀 생소했다 하지만 결과적으로 효율적이다 

DP의 경우, 

현재 확인중인  array[i][j]에 도달할때 이전의 칸으로부터 

가로방향으로 오는지, 세로방향으로 오는지, 대각선 방향으로 오는지 확인해야 한다. 

다만 대각선 방향으로 오는 경우,

array[i-1][j], array[i][j-1], array[i][j] 가 모두 0 인지 (빈칸인지) 확인해야 한다. 

# 17070 DP로 풀어보기 !!

n = int(input())
array = []
for _ in range(n):
    array.append(list(map(int, input().split())))

result = [[[0]*n for _ in range(n)] for _ in range(3)]
result[0][0][1] = 1 # 맨 처음 파이프의 위치

# x == 0 (가로 방)향 인 row 1로 초기화
for i in range(2, n):
    if array[0][i] == 0:
        result[0][0][i] = result[0][0][i-1]

for i in range(1, n):
    for j in range(2, n):
        # 대각선으로 오는 경우 - 양 옆의 세 칸이 모두 빈칸인지 확인
        if array[i][j] == 0 and array[i-1][j] == 0 and array[i][j-1] == 0:
            # 대각선으로 올때 : 가로, 세로 대각선 모두 가능!
            result[2][i][j] = result[0][i-1][j-1] + result[1][i-1][j-1] + result[2][i-1][j-1]

        if array[i][j] == 0:
            # 가로로 올 때 : 가로에서 가로, 대각선에서 가로
            result[0][i][j] = result[0][i][j-1] + result[2][i][j-1]
            # 세로로 올 때 : 세로에서 세로, 대각선에서 세로
            result[1][i][j] = result[1][i-1][j] + result[2][i-1][j]

# 총합 : 가로 세로 대각선 방향
print(result[0][n-1][n-1] + result[1][n-1][n-1] + result[2][n-1][n-1])

ㅋㅋ 궁금해서 비교해봤는데 DP가 메모리도 적게 잡아먹고 시간도 단축된다

DP알고리즘으로 풀면, DFS가 재귀호출 하는것에 비해 역시 효율적이라는걸 깨달았다 

(DFS로 풀면 pypy3에서만 시간초과가 안난다)

사진에서 위에 있는것이 DP로 풀었을 때, 아래있는 것이 DFS로 풀었을 때이다 

 

50일 달성 ! 😆