[백준] 17070 파이프 옮기기1(Python)

1. 생각 정리

• 그림만 보면 되게 복잡한 것 같지만 파이프의 끝부분이 가리키는 좌표 이동하는 느낌으로 생각하면 될 듯
• 이전 단계에서 어떤 방향으로 움직였는지가 다음 방향 선택에 영향을 미친다.
  • 가로 이동 -> 이전에 대각선 or 가로
  • 세로 이동 -> 이전에 대각선 or 세로
  • 대각선 이동 -> 이전에 대각선 or 가로 or 세로

 

2. DFS 풀이(시간 초과)

def dfs(pos):
    global cnt
    x, y, z = pos

    # n,n 도달
    if x == n - 1 and y == n - 1:
        cnt += 1
        
    # 가로 세로 대각선의 경우 대각선 이동
    if x + 1 < n and y + 1 < n:
        if graph[x + 1][y + 1] == 0 and graph[x][y + 1] == 0 and graph[x + 1][y] == 0:
            dfs((x + 1, y + 1, 2))

    # 가로 대각선의 경우 가로 이동
    if z == 0 or z == 2:
        if y + 1 < n:
            if graph[x][y + 1] == 0:
                dfs((x, y + 1, 0))

    # 세로 대각선의 경우 세로 이동
    if z == 1 or z == 2:
        if x + 1 < n:
            if graph[x + 1][y] == 0:
                dfs((x + 1, y, 1))
                
    return cnt


n = int(input())
graph = [[] for _ in range(n)]
cnt = 0
# 그래프 정보 입력
for i in range(n):
    graph[i] = list(map(int, input().split()))

# x,y,현재방향
print(dfs((0, 1, 0)))

 

3. dp 풀이(성공)

• mapp에 좌표 정보를 받고 바깥 경계를 다 1로 채워 넣는다.
• dp는 3차원 리스트로 [행,열,방향 정보]가 mapp과 같은 크기로 들어가 있다.
• 방향정보 (0->가로 / 1->세로 / 2-> 대각선)

n = int(input())

#mapp 입력받기(바깥부분 1로 채워서)
mapp = [[1]*(n+2)]
for i in range(n):
    temp =  list(map(int, input().split()))
    mapp.append([1]+temp+[1])
mapp.append([1]*(n+2))

#dp생성
dp = [[[0,0,0] for _ in range(n+2)] for _ in range(n+2)]
dp[1][2][0] = 1

#확장해니가며 dp 갱신
for c in range(3,n+1): #열
    for r in range(1,n+1): #행
        #이전이 가로, 대각선 -> 가로
        #이전이 세로, 대각선 -> 세로
        #이전이 가로, 세로, 대각선 -> 대각선
        #dp의 3차원 (0->가로 / 1->세로 / 2->대각선)
        
        if mapp[r][c] == 0:
            dp[r][c][0] = dp[r][c-1][0] + dp[r][c-1][2] #가로이동
            dp[r][c][1] = dp[r-1][c][1] + dp[r-1][c][2] #세로이동
            
            if mapp[r-1][c] == 0 and mapp[r][c-1] == 0:
                dp[r][c][2] =  dp[r-1][c-1][0] + dp[r-1][c-1][1] + dp[r-1][c-1][2]#대각선 이동

print(dp[n][n][0] + dp[n][n][1] + dp[n][n][2])