Python - 17070 - 파이프 옮기기 1

파이프 옮기기 1 click

 

내리막길 문제의 응용 버전이다. [내리막길 포스팅]

 

파이프가 가로로 위치하고 있을 때를 0, 대각선으로 위치하고 있을 때를 1 그리고 세로로 위치할 때 2라고 하자.

 

가로와 세로인 경우 해당 칸만 빈칸이라면, 위치시킬 수 있다. 하지만, 대각선인 경우, 해당 칸 위쪽과 왼쪽까지 빈칸이어야 위치시킬 수 있다.

 

• 가로 세로 대각선인 경우를 각각 탐색해 나가야 함으로, 각 칸에 길이 3인 배열을 추가한 3차원 배열(dp)을 만들었다. 이 배열에는 (n,m)으로 갈 수 있는 경우의 수를 저장할 것이다. 
• 방문여부를 확인하기 위해서 dp배열의 초기값은 모두 -1로 설정했다. 방문한 지점은 0으로 변경해주어 방문 여부를 체크하기 위함이다. dp[n-1][m-1]은 [1,1,1]로 설정해 주었다. n,m으로부터 n,m까지 갈 수 있는 방법은 1가지이기 때문이다.
• n,m까지 dfs탐색을 진행하다가 dp의 값이 -1이 아닌 점을 만나면 해당 지점으로부터 n,m까지 갈 수 있는 경로의 수를 현재까지 진행해온 경로에 모두 더해주었다.

 

 

 

 

문제의 입력 예시에서 n,m까지 갈 수 있는 경우들만 함께 살펴보자. dfs탐색을 진행해보자. 

위 그림의 경로로 이동하다가, n,m(dp값이 -1이 아닌 지점)에 도달한다. 도달했음으로, 재귀함수를 한 개씩 종료시키며 지나온 경로에 존재하는 지점의 값에 dp[n-1][m-1]을 모두 더해준다.

 

 

 

 

위의 경로로 이동한 경우에도 n,m(dp값이 -1이 아닌 지점)에 도달했음으로, 지나온 경로들에 dp[n-1][m-1]을 더해준다. 이렇게 되면, dp[0][1][3]에는 2가 저장되게 된다. n,m까지 갈 수 있는 경로의 수가 2라는 의미이다.

 

 

 

 

위의 경로로 이동한 경우에도 n,m(dp값이 -1이 아닌 지점)에 도달했음으로, 지나온 경로들에 dp[n-1][m-1]을 더해준다. 이렇게 되면, dp[0][1][3]에는 3이 저장되게 된다. n,m까지 갈 수 있는 경로의 수가 3이다.

 

 

code

 

import sys
read=sys.stdin.readline
sys.setrecursionlimit(100000)

def dfs(a,b,d):
    if dp[a][b][d] != -1:
        return dp[a][b][d]
        
    #방문한 점의 경우 방문의 표시로 -1에서 0으로 업데이트 해준다.
    dp[a][b][d] = 0
    
    #d가 2인 경우 가로, 1인 경우 대각선, 0인 경우 세로
    
    #d = 2인 경우 가로와 대각선의 경우만 고려한다.
    if d == 2:
        for x,y,new_d in [(0,1,2),(1,1,1)]:
            ax,by = a+x,b+y
            if 0<=ax<n and 0<=by<n and MAP[ax][by] == 0:
                if new_d == 1:
                    if MAP[ax][by-1] == 0 and MAP[ax-1][by] == 0: 
                        dp[a][b][d] += dfs(ax,by,new_d)
                else:
                    dp[a][b][d] += dfs(ax,by,new_d)
    #d = 1인 경우 가로, 세로, 대각선 모두를 고려한다.
    elif d == 1:
        for x,y,new_d in [(0,1,2),(1,1,1),(1,0,0)]:
            ax,by = a+x,b+y
            if 0<=ax<n and 0<=by<n and MAP[ax][by] == 0:
                if new_d == 1:
                    if MAP[ax][by-1] == 0 and MAP[ax-1][by] == 0: 
                        dp[a][b][d] += dfs(ax,by,new_d)
                else:
                    dp[a][b][d] += dfs(ax,by,new_d)
    #d = 0인 경우 대각선과 세로인 경우를 고려한다.                    
    else:
        for x,y,new_d in [(1,1,1),(1,0,0)]:
            ax,by = a+x,b+y
            if 0<=ax<n and 0<=by<n and MAP[ax][by] == 0:
                if new_d == 1:
                    if MAP[ax][by-1] == 0 and MAP[ax-1][by] == 0: 
                        dp[a][b][d] += dfs(ax,by,new_d)
                else:
                    dp[a][b][d] += dfs(ax,by,new_d)
     
    #현재 지점에서 도착지까지 갈 수 있는 경로의 수를 return한다.
    return dp[a][b][d]

n = int(read())
MAP = list(list(map(int,read().split())) for _ in range(n))
#초기값을 -1로 설정
dp = list(list(list(-1 for _ in range(3)) for _ in range(n)) for _ in range(n))
#도착지점에서 도착지점까지 이동하는 경로의 수는 1 임으로 도착지점은 모두 1로 설정해준다. 
dp[-1][-1] = [1,1,1]

print(dfs(0,1,2))

 

틀린 부분이 있을 수 있습니다. 피드백 주시면 고치도록 하겠습니다! 감사합니다.👍

[꼭 다시 풀어보기]