[Python] 17070 - 파이프 옮기기 1

[Gold V] 파이프 옮기기 1 - 17070 

[문제 링크](https://www.acmicpc.net/problem/17070)

🗝️알고리즘 분류

• 다이나믹 프로그래밍
• 그래프 탐색

---

💻문제 정의

파이프를 세 방향으로 놓을 수 있는데, (N, N)까지 놓을 수 있는 경우의 수를 구하는 문제이다.

 

파이프를 놓을 때, 벽을 긁어서는 안되고 90도로 꺾을 수 없다.

 

💡접근 및 설계

그래프 전체를 탐색하며 파이프를 놓을 수 있는 경우의 수를 저장하는 방식으로 접근하였다.

또한, 파이프가 놓일 당시에 모양(가로, 세로, 대각)에 따라 다음 파이프가 놓일 수 있는 경우가 달라지므로 이를 따로 저장하도록 하였다.

 

✏️알고리즘 풀이

# 0 : 가로, 1 : 세로, 2 : 대각
dp = [[[0] * 3 for _ in range(N)] for _ in range(N)]
dp[0][1][0] = 1

for i in range(N):
    for j in range(2, N):
        if graph[i][j] == 1:
            continue
        
        # 가로
        if (graph[i][j] == 0):
            dp[i][j][0] = dp[i][j-1][0] + dp[i][j-1][2]

        # 세로
        if (i > 0) and (graph[i-1][j] == 0):
            dp[i][j][1] = dp[i-1][j][1] + dp[i-1][j][2]

        # 대각선
        if (i > 0) and (graph[i][j-1] == 0) and (graph[i-1][j] == 0):
            dp[i][j][2] = dp[i-1][j-1][0] + dp[i-1][j-1][1] + dp[i-1][j-1][2]

 

벽을 만날경우 continue.

 

현재의 점에 가로 파이프가 놓이는 경우는, 이전 파이프가 가로 또는 대각으로 놓인 경우이다. 그렇기에 dp에 저장된 값 중, 가로와 대각의 경우만을 고려한다.

 

세로의 경우도 마찬가지이다.

 

현재의 점에 대각이 놓일 경우는, 이전의 점과 현재의 점을 포함하는 2x2 크기 내에 벽이 존재하면 안된다. (파이프를 회전할 때 벽을 긁으면 안된다.) 해당 내용을 조건으로 두고 대각의 경우는 이전 파이프의 모양이 어느것이 되어도 가능한 경우이기에 모든 경우를 고려한다.

 

🗒️제출 코드

# 17070 파이프 옮기기

N = int(input())

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

# 0 : 가로, 1 : 세로, 2 : 대각
dp = [[[0] * 3 for _ in range(N)] for _ in range(N)]
dp[0][1][0] = 1

for i in range(N):
    for j in range(2, N):
        if graph[i][j] == 1:
            continue
        
        # 가로
        if (graph[i][j] == 0):
            dp[i][j][0] = dp[i][j-1][0] + dp[i][j-1][2]

        # 세로
        if (i > 0) and (graph[i-1][j] == 0):
            dp[i][j][1] = dp[i-1][j][1] + dp[i-1][j][2]

        # 대각선
        if (i > 0) and (graph[i][j-1] == 0) and (graph[i-1][j] == 0):
            dp[i][j][2] = dp[i-1][j-1][0] + dp[i-1][j-1][1] + dp[i-1][j-1][2]

print(sum(dp[N-1][N-1]))

---