[백준 파이썬] 17070파이프 옮기기 1

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

17070번: 파이프 옮기기 1

문제



 

파이프를 옮긴 후 적절하게 회전시켜 마지막 좌표로 이동시키는 경우의 수를 구하는 문제이다.

---

풀이

파이프를 이동시켜 지정한 위치까지 옮겨야한다.

이 때 파이프는 45도까지 회전시킬 수 있는데 중요한 점은 이동 후 회전시킬 수 있다는 점이다.

따라서 같은자리에서 회전은 불가능하고 현재 파이프가 놓여있는 방향으로 한칸 이동 후 회전시켜야 한다.

 

파이프가 이동할 수 있는 경로의 모든 경우의수는 위의 사진과 같다.

이 때 이동하기 전에 파이프가 어떤 방향으로 놓여있는지에 따라 이동한 뒤에 방향을 결정할 수 있다.

예를들어 이동전 방향이 "가로" 인 경우 가로 -> 대각선 또는 가로 -> 가로 의 방향으로 이동할 수 있다.

 

이를 이용하여 이전 좌표에서 어떤 방향이였는에 따라 다음좌표에 "가능한 방향의 경우의수"를 입력하는게 가능하다.

 

예를들어 위의 사진의 경우 r, c가 0, 1인 좌표에서 이동하므로
0, 2좌표에 가로 파이프 경우의수가 1이 추가되고

1, 2좌표에 대각선 파이프 경우의수가 1이 추가된다.

해당 방식을 이용하여 모든 경우의 수를 구할 수 있다.

모든 좌표는 파이프 끝을 기준으로 한다.

 

경우의 수를 구하기 위해 규칙을 정리하면 다음과 같다.

1. r, c의 가로파이프의 개수 = (r, c-1의 가로 파이프의 개수) + (r, c-1의 대각선 파이프의 개수)

2. r, c의 세로파이프의 개수 = (r-1, c의 세로 파이프의 개수) + (r-1, c의 대각선 파이프의 개수)

3. r, c의 대각선파이프의 개수 = (r-1, c-1 가로파이프 개수) + (r-1, c-1 세로파이프의 개수) + (r-1, c-1 대각선 파이프의 개수)

 

해당 규칙을 적용하려면 모든 좌표가 가로 파이프, 세로파이프, 대각선 파이프의 개수를 가지고 있어야 한다.

따라서 3차원 배열을 사용하여 입력해주었다.

r, c에서의 가로파이프의 경우의수는 graph[r][c][0] 의 식으로 구할 수 있다.

 

이제 해당 규칙을 적용시켜 문제를 풀 수 있는데, 가장 먼저 초기세팅을 해주어야한다.

첫번 째 파이프의 위치는 고정이며 방향도 가로로 고정이므로 

r = 0일 때 즉 첫번째 줄에는 끝이 가로인 방향의 파이프밖에 올 수 없다.

이를 이용해서 처음 값을 초기화해준다.

 

#초기 세팅
dp[0][1][0] = 1
for i in range(2, N):
    if graph[0][i] == 0:
        dp[0][i][0] = dp[0][i-1][0]

벽이 있는 경우는 이동할 수 없으므로 graph[r][c] 가 0인지 확인한 후 가로 파이프의 경우의 수를 증가해준다.

 

이 후 배열을 순회하며 위의 규칙에 따라 파이프의 개수를 증가시켜준다.

for i in range(1, N):
    for j in range(1, N):
        if graph[i][j] == 0:
            #대각선 파이프 추가
            if graph[i-1][j] == 0 and graph[i][j-1] == 0:
                dp[i][j][2] = dp[i-1][j-1][0] + dp[i-1][j-1][1] + dp[i-1][j-1][2]
            
            #가로 및 세로 파이프 추가
            dp[i][j][0] = dp[i][j-1][0] + dp[i][j-1][2]
            dp[i][j][1] = dp[i-1][j][1] + dp[i-1][j][2]

이 때 1, 1 에서부터 시작하는 이유는 

r = 0일 때는 위에서와 같이 가로파이프의 경우의수를 먼저 세팅해주었기 때문이고

c = 0일 때는 어떤 파이프도 위치할 수 없기 때문이다.

 

해당 배열을 순회하고 나면 

graph[r][c][0], graph[r][c][1], graph[r][c][2] 에 각각 가로, 세로, 대각선 파이프의 경우의 수가 입력되게 된다.

이를 모두 더하면 가능한 경우의 수가 나오게 된다.

 

코드

N = int(input())

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

dp = [[[0, 0, 0] for _ in range(N)] for _ in range(N)]

#초기 세팅
dp[0][1][0] = 1
for i in range(2, N):
    if graph[0][i] == 0:
        dp[0][i][0] = dp[0][i-1][0]
    

for i in range(1, N):
    for j in range(1, N):
        if graph[i][j] == 0:
            #대각선 파이프 추가
            if graph[i-1][j] == 0 and graph[i][j-1] == 0:
                dp[i][j][2] = dp[i-1][j-1][0] + dp[i-1][j-1][1] + dp[i-1][j-1][2]
            
            #가로 및 세로 파이프 추가
            dp[i][j][0] = dp[i][j-1][0] + dp[i][j-1][2]
            dp[i][j][1] = dp[i-1][j][1] + dp[i-1][j][2]
            

print(dp[N-1][N-1][0] + dp[N-1][N-1][1] + dp[N-1][N-1][2])