💻 백준 17070: 파이프 옮기기 1

문제 소개 🧐

N×N 크기의 집에서 2칸을 차지하는 파이프를 (1, 2) 위치에서 (N, N) 위치까지 옮기는 경우의 수를 찾는 문제다. 파이프는 가로, 세로, 대각선 3가지 상태를 가질 수 있으며, 각 상태에 따라 이동할 수 있는 방향이 정해져 있다. 파이프는 항상 빈 칸만 차지해야 한다.

입력 📝

  • 첫째 줄: 집의 크기 N (3 ≤ N ≤ 16)
  • 둘째 줄부터 N개의 줄: 집의 상태 (0은 빈 칸, 1은 벽)

출력 📤

파이프의 한쪽 끝을 (N, N)으로 이동시키는 방법의 수를 출력한다.

제한 ❌

  • 시간: 1초
  • 메모리: 512 MB

나의 풀이 과정 🌊

첫 번째 시도: BFS

Idea:
처음에는 이 문제를 그래프 탐색 문제로 보고 BFS(너비 우선 탐색)로 접근했다. 큐에 (현재 파이프 끝 좌표, 파이프 방향)을 저장하고, 각 상태에서 이동할 수 있는 모든 경우를 탐색하여 (N, N)에 도달할 때마다 카운트를 1씩 증가시키는 방식이다.

파이프의 방향(가로: 0, 대각선: 1, 세로: 2)에 따라 다음에 이동할 수 있는 방향과 좌표, 그리고 벽을 체크하는 조건을 꼼꼼하게 설정하여 구현했다.

Code:

import sys
from collections import deque

n = int(sys.stdin.readline().rstrip())
house = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]

# 각 방향(가로, 대각선, 세로)에서 이동 가능한 다음 방향들
# (dr, dc)와 다음 방향(nd)을 튜플로 묶어 관리하면 더 깔끔했을 것 같다.
move = [[(0, 1), (1,1)], [(0, 1), (1,1), (1,0)], [(1,0), (1,1)]]  # 가로, 대각선, 세로
start_pos = (0,1)
q = deque()
q.append((start_pos, 0))  # (현재 좌표, 파이프 방향)

answer = 0
while q:
    cur_pos, direction = q.popleft()
    r, c = cur_pos
    if r == n-1 and c == n-1:
        answer += 1
        continue # 도착했으면 더 이상 진행 안 함

    # 현재 방향에서 가능한 다음 움직임들을 탐색
    for dr, dc in move[direction]:
        n_r, n_c = r + dr, c + dc

        if n_r >= n or n_c >= n or house[n_r][n_c] == 1:
            continue

        # 다음 파이프 방향 결정
        n_dr = 0
        if dr == 1 and dc == 1: # 대각선
            n_dr = 1
            # 대각선 이동 시에는 추가로 2칸의 벽을 더 확인해야 함
            if house[n_r-1][n_c] == 1 or house[n_r][n_c-1] == 1:
                continue
        elif dr == 1 and dc == 0: # 세로
            n_dr = 2
        else: # 가로
            n_dr = 0

        q.append(((n_r, n_c), n_dr))

print(answer)

Result: 시간 초과 😭

BFS로 모든 경로를 탐색하다 보니, N이 커질수록 중복되는 계산이 많아져 시간 초과가 발생한 것 같다.

두 번째 시도: DP (다이나믹 프로그래밍)

Idea:
BFS의 시간 초과를 겪고 나서, 이 문제는 DP로 풀어야 한다는 것을 깨달았다. (N, N)까지 도달하는 경우의 수를 누적해서 계산하는 방식이 더 효율적이다.

3차원 DP 테이블 dp[x][y][dir]를 ‘파이프의 끝이 (x, y)에 있고, 방향이 dir일 때의 경우의 수’로 정의했다.

  • 가로 (dir=0): dp[i][j][0] = dp[i][j-1][0] + dp[i][j-1][2]
  • 세로 (dir=1): dp[i][j][1] = dp[i-1][j][1] + dp[i-1][j][2]
  • 대각선 (dir=2): dp[i][j][2] = dp[i-1][j-1][0] + dp[i-1][j-1][1] + dp[i-1][j-1][2]

위 점화식을 기반으로 DP 테이블을 채워나가면 최종적으로 dp[n-1][n-1]에 있는 모든 방향의 경우의 수를 합산하여 답을 구할 수 있다.

Code:

import sys
from collections import deque

n = int(sys.stdin.readline().rstrip())
house = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]

dp = [[[0 for _ in range(3)] for _ in range(n)] for _ in range(n)]  # 가로 세로 대각 의 형태로 온 경우의 수
dp[0][1][0] = 1  # 가로로 놓여있으니깐

for i in range(2,n):  # 첫행 채워주기
    if house[0][i] == 1:
        break
    dp[0][i][0] = dp[0][i-1][0]

for i in range(1, n):  # dp[i][j] = max(dp[i-1][j][1] + dp[i-1][j][2], dp[i][j-1][0] + dp[i][j-1][2], dp[i-1][j-1][2])
    for j in range(1, n):
        if house[i][j] == 0:
            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]
            
            if house[i-1][j] == 0 and house[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]

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

Result: 성공! ✅

DP를 사용하니 중복 계산을 피하고 효율적으로 경우의 수를 누적하여 시간 내에 문제를 해결할 수 있었다.

배운 점 및 느낀 점 ✍️

  • BFS vs DP: 경로의 ‘수’를 구하는 문제는 BFS/DFS로 모든 경로를 탐색하면 시간 초과가 발생하기 쉽다. 이럴 땐 DP로 점화식을 세워 접근하는 것이 훨씬 효율적이라는 것을 다시 한번 느꼈다.
  • 상태 정의의 중요성: DP 문제를 풀 때 dp 테이블의 상태를 어떻게 정의하느냐가 가장 중요하다. 이 문제에서는 (x, y, 방향) 3가지를 상태로 정의해야 했다.
  • 꼼꼼한 조건 체크: 특히 대각선으로 이동할 때는 추가로 확인해야 할 벽이 있다는 점을 놓치기 쉬웠다. DP 점화식을 세울 때 항상 모든 제약 조건을 꼼꼼히 반영해야겠다.