[baekjoon] 백준 1520 내려막길

문제

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

1520번: 내리막 길

풀이

dfs, dp 문제이다. 처음에는 dfs로 풀고자 하였지만 계속해서 시간초과가 났다. dfs탐색만으로 문제를 수행하게 되면 이미 탐색한 곳을 다시 한번 탐색하게 되면서 시간 초과가 나오게 된다. 그래서 탐색 한 곳을 탐색 처리하게 되면 다시 이어서 방문하지 않아 여러가지 경우의 수를 구할 수 없다. 그래서 dp 초기값을 -1로 초기화하고 탐색 시 0으로 초기화해주어 탐색하였다.

• dp 배열의 모든 초기값을 -1로 초기화
• 각 칸을 탐색 시 0으로 초기화해주어 탐색 유무를 판단하고 목적지에 도착하면 1 반환
• dp값이 -1이라면 탐색하지 않은 곳으로 탐색
• dp값이 1 이상의 값이라면 이전에 도착지까지 방문한 값으로 dp값을 리턴받아 다시는 그 경로를 탐색하지 않게 한다.

코드

# 내리막길
# dfs로 구현 
# 도착할 경우 남아있는 stack 저장
# visited를 초기화 한 후 stack에 있는 경우의 수를 다시 출발

M, N = map(int, input().split(" "))
array = []
for _ in range(M):
    array.append(list(map(int, input().split())))

dp = [[-1 for _ in range(N)] for _ in range(M)]
direction = [(1,0), (-1,0), (0,1), (0,-1)]

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

    if dp[x][y] == -1:
        dp[x][y] = 0

        for dx, dy in direction:
            nx = x + dx
            ny = y + dy

            if 0 <= nx < M and 0 <= ny < N:
                if array[x][y] > array[nx][ny]:
                    dp[x][y] += dfs(nx, ny)

    return dp[x][y]



print(dfs(0,0))

실패코드

M, N = map(int, input().split(" "))
array = []
for _ in range(M):
    array.append(list(map(int, input().split())))


direction = [(1,0), (-1,0), (0,1), (0,-1)]

def dfs(array, start_node):
    visited = [[False for i in range(N)] for i in range(M)]
    stack = [start_node]

    while(stack):
        # for i in range(len(visited)):
            # print(visited[i])

        x, y = stack.pop()
        visited[x][y] = True

        if x == M-1 and y == N-1:
                memory.extend(stack)
                return 1

        for dx, dy in direction:
            nx = x + dx
            ny = y + dy

            if nx < 0 or nx >= M or ny < 0 or ny >= N:
                continue

            if array[nx][ny] < array[x][y] and not visited[nx][ny]:
                if not visited[nx][ny]:
                    stack.append((nx, ny))
                else:
                    return 1
                # print("stack",stack)

    return 0
memory = [(0,0)]
result = 0
while(memory):
    cnt = dfs(array,memory[0])
    del memory[0]
    # print("memeory",memory)
    result += cnt
    # print("==============")
print(result)

ㄱ