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

📖 문제

---

🧑🏻‍💻 풀이 과정

1) 문제 이해 및 접근

처음에 문제를 접하고 간단하게 BFS 방식으로 탐색을 시도하였습니다.

그러나 모든 경우를 탐색하여야 하므로 시간 초과가 발생하였습니다.

 

그 이후 각 좌표에 올 수 있는 경우의 수를 구하는 방식으로 풀이하였습니다.

2) 알고리즘

• 다이나믹 프로그래밍

3) 풀이 코드

사용 언어 - Python

import sys
sys.stdin = open('input.txt')

N = int(sys.stdin.readline())                                               # 가로, 세로 길이
home = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]     # 집의 상태 0-빈칸, 1-벽
dp = [[[0] * (N+1) for _ in range(N+1)] for _ in range(3)]                  # 가로, 대각선, 세로

dp[0][1][2] = 1                                                                     # 처음에 (1, 1)과 (1, 2)를 차지하고 있으므로 가로 방향 1,2 경우의 수 1개
for i in range(1, N+1):                                                             # 1행부터 시작, 3열부터 시작
    for j in range(3, N+1):                                                         
        if home[i-1][j-1] == 0:                                                     # 다음에 놓을 칸이 빈 칸일때만
            dp[0][i][j] = dp[0][i][j-1] + dp[1][i][j-1]                             # 가로로 놓는 경우의 수 = 왼쪽 열의 가로 경우의 수 + 왼쪽 열의 대각선 경우의 수
            dp[2][i][j] = dp[2][i-1][j] + dp[1][i-1][j]                             # 세로로 놓는 경우의 수 = 위쪽 행의 세로 경우의 수 + 위쪽 행의 대각선 경우의 수
            if home[i-2][j-1] == 0 and home[i-1][j-2] == 0:                         # 대각선으로 놓을때 주변 4칸이 빈칸이여야 함
                dp[1][i][j] = dp[0][i-1][j-1] + dp[1][i-1][j-1] + dp[2][i-1][j-1]   # 대각선 놓는 경우의 수 = 왼쪽 위의 가로, 세로, 대각선 경우의 수를 모두 합함

print(dp[0][N][N] + dp[1][N][N] + dp[2][N][N])          # N, N 의 가로, 세로, 대각선의 모든 경우의 수를 더함

---

📝 결과 및 학습한 내용

1) 어려웠던 내용

특별히 없습니다.

2) 새롭게 학습한 내용

특별히 없습니다.

---

🔗 문제 링크

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

17070번: 파이프 옮기기 1

 

 

※ 오류 및 오타, 다른 의견이 있는 경우 댓글을 남겨주시면 감사하겠습니다