[백준 BOJ / Python] 17070번 파이프 옮기기 1

문제

n*n 크기의 새 집이 있다. 집 수리를 위해 파이프를 옮겨야 하는데, 파이프는 무겁기 때문에 밀어서 이동시켜야 한다.
파이프는 2개의 연속된 칸을 차지하는 크기이며 3가지 방향으로 회전이 가능하다.

파이프를 밀 수 있는 방향은 →, ↘, ↓ 방향 총 3가지가 있으며, 회전은 45도만 가능하다.
따라서 다음 그림과 같이 가로일 때 2가지, 세로일 때 2가지, 대각선일 때 3가지가 있다.

또한 벽(1)으로는 파이프를 이동시킬 수 없다.

가장 처음에는 파이프가 가로 방향으로 왼쪽 상단에 위치해 있다. 파이프의 한쪽을 (n,n)으로 이동시키는 방법의 개수를 구하여라.

풀이

• DP를 사용해 문제를 풀 수 있다.
• 마지막 위치(n,n)에 파이프가 도달할 수 있는 경우의 수 문제를
• (i,j)에 파이프가 도달할 수 있는 경우의 수 문제로 분할할 수 있다.
• 현재 위치(i,j)에 어떤 상태의 파이프가 도달할 수 있는가를 고려한다면 다음과 같은 경우를 도출할 수 있다.
  • 가로 파이프가 도달할 수 있는 경우 : 이전 파이프가 가로 혹은 대각선 방향이었을 경우
  • 세로 파이프가 도달할 수 있는 경우 : 이전 파이프가 세로 혹은 대각선 방향이었을 경우
  • 대각선 파이프가 도달할 수 있는 경우 : 이전 파이프가 가로 혹은 세로 혹은 대각선 방향이었을 경우
    (대각선일때 주변 칸에 벽이 없어야함)

가로

세로

대각선

• 이를 점화식으로 다시 표현하면 다음과 같다.
  • dp[i][j][가로] += dp[i][j-1][가로] + dp[i][j-1][대각선]
  • dp[i][j][세로] += dp[i-1][j][세로] + dp[i-1][j][대각선]
  • dp[i][j][대각선] += dp[i-1][j-1][가로] + dp[i-1][j-1][세로] + dp[i-1][j-1][대각선]
• 여기서 두 가지 조건에 유의해야 한다.
  • 집 영역을 벗어나지 않는지
  • 대각선은 총 4칸 모두 벽이 아닌지

Python 코드

n = int(input())
# 벽 정보
wall = [list(map(int,input().split())) for _ in range(n)]

# dp[row][col][dir]
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(1,n):
        if wall[i][j]: # 현재 위치에 벽이 있다면 넘어감
            continue

        # 오른쪽 이동 : 오른쪽 -> 오른쪽 / 대각선 -> 오른쪽
        dp[i][j][0] += dp[i][j-1][0] + dp[i][j-1][2]

        if i-1 < 0: # 범위 밖 제외
            continue
        # 아래쪽 이동 : 아래쪽 -> 아래쪽 / 대각선 -> 아래쪽
        dp[i][j][1] += dp[i-1][j][1] + dp[i-1][j][2]

        if wall[i-1][j] or wall[i][j-1]: # 대각선은 주변에 벽도 체크해줘야함
            continue
        # 대각선 이동 : 모든 경우 -> 대각선
        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]))

 

문제출처

 

17070번: 파이프 옮기기 1