[python] 백준 - 17070 (파이프 옮기기1)

2026.01.15ko 0 시리즈 · 알고리즘 #알고리즘

골드5 문제이며, 제한 시간은 1초이다.

문제

해결 과정

경로의 수를 구하는 문제이기에 DFS로 접근했다. DFS를 돌리면서 현재 방향까지 인자로 넘겨주고, 그 방향에 맞게 동작하도록 했다. 주요 아이디어는 가로로 갈 수 있는 방향, 세로로 갈 수 있는 방향이 있고, 대각선은 모든 방향이 다 갈 수 있다. 따라서

가로인 경우 가로, 대각 탐색 및 빈 칸 체크
세로인 경우 세로, 대각 탐색 및 빈 칸 체크
대각선인 경우 모두 탐색 및 빈 칸 체크 이후 DP테이블에 현재 그 위치와 그 방향에서 목적지까지 가는 방법의 수를 저장하고, DP테이블을 갱신하며 재귀를 돌린다. 마지막에 목적지의 DP테이블 값을 출력한다.

풀이

import sys
input = sys.stdin.readline

def dfs(x, y, d):
  if x == n - 1 and y == n - 1:
    return 1
  
  if dp[x][y][d] != -1:
    return dp[x][y][d]
    
  dp[x][y][d] = 0
  #오른쪽 갈 수 있는 경우
  if d in (0, 1) and y + 1 < n and graph[x][y + 1] == 0:
      dp[x][y][d] += dfs(x, y + 1, 0)
  #아래로 갈 수 있는 경우
  if d in (1, 2) and x + 1 < n and graph[x + 1][y] == 0:
      dp[x][y][d] += dfs(x + 1, y, 2)
  #오른쪽 대각선 갈 수 있는 경우
  if x + 1 < n and y + 1 < n and graph[x + 1][y] == 0 and graph[x][y + 1] == 0 and graph[x + 1][y + 1] == 0:
    dp[x][y][d] += dfs(x + 1, y + 1, 1)
  return dp[x][y][d]

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

if graph[n - 1][n - 1] == 1:
  print(0)
  exit(0)

dp = [[[-1 for _ in range(3)] for _ in range(n)] for _ in range(n)]
#오른쪽 0, 대각 1, 아래 2
print(dfs(0, 1, 0))

아이디어는 쉬운데 dp를 사용해야 시간복잡도 측면에서 안정적이다. 아이디어가 쉬워서 골드5 문제인 것 같다.

아직 댓글이 없습니다.

문제

해결 과정

풀이

댓글

댓글 쓰기