백준 17070번: 파이프 옮기기 1(파이썬, Python, DFS, DP)

문제에는 사진이 많으므로... 직접 보는 것을 추천

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

일단 문제 자체는 되게 쉬워보였는데, 시간 제한이 문제였다.

아무리 끙끙대도 못풀어서 GPT한테 물어본 결과... 그래프 탐색 + DP 문제라고 한다.(이게 골드5?)

어후 DP만 들어가면 더럽게 어렵다...

import sys
sys.setrecursionlimit(10**6)

N = int(sys.stdin.readline().strip())

maps = [list(map(int,sys.stdin.readline().split())) for _ in range(N)]
dp = [[[-1 for _ in range(N)] for _ in range(N)] for _ in range(3)]

# 우, 대각, 하
dx = [0,1,1]
dy = [1,1,0]

def dfs(x, y, state):
    if x == N -1 and y == N-1:
        return 1

    if dp[state][x][y] != -1:
        return dp[state][x][y]

    ways = 0
    # state = 0 가로
    if state == 0 :
        for i in range(2):
            nx = x + dx[i]
            ny = y + dy[i]

            if 0 <= nx < N and 0 <= ny < N and maps[nx][ny] != 1:
                # i == 1 대각 -> state = 2
                if i == 1:
                    if maps[nx-1][ny] != 1 and maps[nx][ny-1] != 1:
                        ways += dfs(nx, ny, 2)
                # i == 0 가로 -> state = 0 
                else:
                    ways += dfs(nx, ny, 0)
                
    # 세로
    elif state == 1:
        for i in range(1,3):
            nx = x + dx[i]
            ny = y + dy[i]

            if 0 <= nx < N and 0 <= ny < N and maps[nx][ny] != 1:
                if i == 1:
                    if maps[nx-1][ny] != 1 and maps[nx][ny-1] != 1:
                        ways += dfs(nx, ny, 2)
                else:
                    ways += dfs(nx, ny, 1)
            
    # 대각
    elif state == 2:
        for i in range(3):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < N and 0 <= ny < N and maps[nx][ny] != 1:
                if i == 0:
                    ways += dfs(nx, ny, 0)
                elif i == 1:
                    if maps[nx-1][ny] != 1 and maps[nx][ny-1] != 1:
                        ways += dfs(nx, ny, 2)
                else :
                    ways += dfs(nx, ny, 1)

    dp[state][x][y] = ways
    return ways
    
         
dfs(0,1,0)
print(max(dp[0][0][1],dp[1][0][1],dp[2][0][1]))

import sys sys.setrecursionlimit(10**6) N = int(sys.stdin.readline().strip()) maps = [list(map(int,sys.stdin.readline().split())) for _ in range(N)] dp = [[[-1 for _ in range(N)] for _ in range(N)] for _ in range(3)] # 우, 대각, 하 dx = [0,1,1] dy = [1,1,0] def dfs(x, y, state): if x == N -1 and y == N-1: return 1 if dp[state][x][y] != -1: return dp[state][x][y] ways = 0 # state = 0 가로 if state == 0 : for i in range(2): nx = x + dx[i] ny = y + dy[i] if 0 <= nx < N and 0 <= ny < N and maps[nx][ny] != 1: # i == 1 대각 -> state = 2 if i == 1: if maps[nx-1][ny] != 1 and maps[nx][ny-1] != 1: ways += dfs(nx, ny, 2) # i == 0 가로 -> state = 0 else: ways += dfs(nx, ny, 0) # 세로 elif state == 1: for i in range(1,3): nx = x + dx[i] ny = y + dy[i] if 0 <= nx < N and 0 <= ny < N and maps[nx][ny] != 1: if i == 1: if maps[nx-1][ny] != 1 and maps[nx][ny-1] != 1: ways += dfs(nx, ny, 2) else: ways += dfs(nx, ny, 1) # 대각 elif state == 2: for i in range(3): nx = x + dx[i] ny = y + dy[i] if 0 <= nx < N and 0 <= ny < N and maps[nx][ny] != 1: if i == 0: ways += dfs(nx, ny, 0) elif i == 1: if maps[nx-1][ny] != 1 and maps[nx][ny-1] != 1: ways += dfs(nx, ny, 2) else : ways += dfs(nx, ny, 1) dp[state][x][y] = ways return ways dfs(0,1,0) print(max(dp[0][0][1],dp[1][0][1],dp[2][0][1]))