[Graph, DFS, DP] 내리막길 - 백준

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

1520번: 내리막 길

 

문제풀이

---

다음 문제는 앞에서 많이 다루었던 일반적인 그래프 문제와 유사했습니다

 

하지만 여기서 주의할 점은 바로

경우의 수를 구하는 문제였습니다.

 

그래서 여기서 생각한 아이디어는

방문한 모든 경우를 global 변수 값에 저장하면

바로 그 경우가 모든 경우의 수를 count하는 것으로 생각했습니다.

 

그래서 처음 제출을 시도한 코드는 다음과 같았습니다

n, m = [int(x) for x in input().split()]

maps = {}
for i in range(0, n) :
    maps[i] = [int(x) for x in input().split()]

global cnt
cnt = 0

def search(row, col, memo={}) :
    global cnt
    if (row, col) == (n-1, m-1) :
        cnt += 1
        return 
    a = False; b= False; c = False; d = False;
    cnt1 = 0; cnt2 = 0; cnt3 = 0; cnt4 = 0;
    if col != m-1 :
        a = True
    if col != 0 :
        b = True
    if row != n-1 :
        c = True
    if row != 0 :
        d = True
    if a :
        diff = maps[row][col] - maps[row][col+1]
        if diff > 0 :
            search(row, col+1, memo)
    if b :
        diff = maps[row][col] - maps[row][col-1]
        if diff > 0 :
            search(row, col-1, memo)
    if c :
        diff = maps[row][col] - maps[row+1][col]
        if diff > 0 :
            search(row+1,col, memo)
    if d :
        diff = maps[row][col] - maps[row-1][col]
        if diff > 0 :
            search(row-1,col, memo)
    return 
search(0,0)  
print(cnt)

 

하지만 시간 초과가 떴습니다

 

그래서 방문한 노드의 계산 값은 이미 알고 있으므로 그 경우는 memo에 따로 저장해주어 또 searching을 하지 않고 바로 저장한 값을 도출하는 메커니즘을 구현하여 문제를 풀었습니다. (memoization)

n, m = [int(x) for x in input().split()]

maps = {}
for i in range(0, n) :
    maps[i] = [int(x) for x in input().split()]

global cnt
cnt = 0

def search(row, col, memo={}) :
    if (row,col) in memo :
        return memo[(row,col)]
    global cnt
    if (row, col) == (n-1, m-1) :
        cnt += 1
        return cnt
    a = False; b= False; c = False; d = False;
    cnt1 = 0; cnt2 = 0; cnt3 = 0; cnt4 = 0;
    if col != m-1 :
        a = True
    if col != 0 :
        b = True
    if row != n-1 :
        c = True
    if row != 0 :
        d = True
    if a :
        diff = maps[row][col] - maps[row][col+1]
        if diff > 0 :
            cnt1 = search(row, col+1, memo)
            cnt = 0
    if b :
        diff = maps[row][col] - maps[row][col-1]
        if diff > 0 :
            cnt2 = search(row, col-1, memo)
            cnt = 0
    if c :
        diff = maps[row][col] - maps[row+1][col]
        if diff > 0 :
            cnt3 = search(row+1,col, memo)
            cnt = 0
    if d :
        diff = maps[row][col] - maps[row-1][col]
        if diff > 0 :
            cnt4 = search(row-1,col, memo)
            cnt = 0
    memo[(row, col)] = cnt1+cnt2+cnt3+cnt4
    return cnt1+cnt2+cnt3+cnt4
result = 0
result = search(0,0)  
print(result)