[알고리즘/동적 계획법] 17070번 : 파이프 옮기기 1 - python

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

17070번: 파이프 옮기기 1

 

---

• 문제
• 소요시간: 실패

---

• 설계하기(접근방법) 

1. 입력받기

행열을 입력받는다

 

2. 구현하기

BFS로 풀어보려다가 도저히 방법이 떠오르지 않아서

다른 블로그의 풀이를 참고했다.

 

이 문제의 핵심은 case를

가로

세로

대각선으로 나누어서 푸는 것이다

 

dp 리스트를 선언할 때

dp = [[[0,0,0] for _ in range(n)] for _ in range(n)] 과 같이

가로, 세로, 대각선의 케이스를 저장할 수 있도록 한다

 

처음 행은 모두 가로 파이프만 가능하기 때문에

모든 첫 가로행은 가로막는 벽이 없다면 이전의 dp로 초기화해준다

 

이 방법은 전에 벽이 없다면 계속 이어지고 = 1

만약 벽이 있었다면 파이프는 위로 올라가질 못하기 때문에 그 뒤로는 막힌다 = 0

 

첫 열 역시 파이프가 갈 수 없기 때문에 0으로 두면 되고

첫행과 첫 열을 초기화 했으니

 

dp를 각각 1부터 순차적으로 순회한다

for x in range(1,n):

    for y in range(1,n):

....

 

매 dp를 순회하면서 현재 위치에 벽이 없다면

1. 현재 파이프가 가로일 때의 케이스는

-> y -1 즉 전 열의 파이프 케이스의 가로일 때와 대각선일 때(문제의 조건)

 

2. 현재  파이프가 가로일 때의 케이스는

-> x - 1 즉 전 행의 파이프가 세로 혹은 대각선일 때

 

3. 현재 파이프가 대각선일 때는

이전 행과 이전 열에 벽이 있으면 안되는 조건이 있으므로

이전 행과 이전 열의 벽을 검사해주고

-> x-1,  y-1 의 가로, 세로, 대각선일 때의 dp를 더해주면 된다

 

 

이 방법은 이전에 벽이 있었더라면 가로, 세로의 경우

이전의 dp도 0이기 때문에 이전 벽은 검사해주지 않아도 된다

즉 벽이 있는 공간(불가능한 공간)의 케이스를 더한다는 사실이 

0을 더하는 것이기 때문에 현재 결과에 영향을 미치지 않아도 된다.

 

 

 

3. 출력하기

dp를 순회한 후 마지막 n-1,n-1의

가로, 세로, 대각선 케이스의 합을 구한다

 

 

 

---

• 코드(출력)

from collections import deque
n = int(input())
home = [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 home[0][i] == 0:
        dp[0][i][0] = dp[0][i-1][0]

for x in range(1, n):
    for y in range(1, n):
        if home[x][y] == 0 and home[x-1][y] == 0 and home[x][y-1] == 0:
            dp[x][y][2] =  dp[x-1][y-1][0] + dp[x-1][y-1][1] + dp[x-1][y-1][2]
        if home[x][y] == 0:
            dp[x][y][0] = dp[x][y-1][0] + dp[x][y-1][2]
            dp[x][y][1] = dp[x-1][y][1] + dp[x-1][y][2]


result = sum(dp[n-1][n-1][i] for i in range(3))
print(result)

---

• 얻어갈 부분

1. 이해하고 독해하는데 오래 걸린 문제이다. 비슷한 유형이 나왔을 때는 이 풀이를 차근차근 떠올려보자