[DFS/DP] MAP 형태에서 DFS와 DP를 활용한 대표예제

전에 풀었던 유형이지만 코테를 대비해서 체화하기 위해 문제를 다시 풀어보았다. 

2X2 그리드로 주어지는 MAP 형태에서 DFS, DP를 사용하는 경우 보통 "~한 경우의 수"를 구하는 문제에서 주로 출제된다.

즉, count+=1를 종점에 도착했을 때마다 더해주어 이를 누적하는 식의 유형이다.

 

또한 memoization을 활용하여 방문한 그리드는 memo에 바로 return해주는 DP의 경우를 바로 사용하는 예제 또한 중요하다.

아래 두 문제가 대표 예시이다. 
코드의 얼개를 기억하고 바로바로 구현할 수 있도록 체화하자.

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

1520번: 내리막 길

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

move_x = [-1,1,0,0]
move_y = [0,0,1,-1]

def DFS(x, y, memo={}) :
    ## 변수 정의, 4 방향으로 쭉 searching해온 경로 값이 누적
    cnt = 0

    ### 종점
    if (x,y) == (m-1,n-1) :
        cnt += 1
        return cnt

    if (x,y) in memo :
        return memo[(x,y)]

    for i in range(4) :
        after_x = x+move_x[i]
        after_y = y+move_y[i]

        if after_x < 0 or after_y < 0 or after_x >= m or after_y >= n :
            continue

        if maps[after_x][after_y] < maps[x][y] :
            cnt += DFS(after_x,after_y,memo)

    ### Memoization
    memo[(x,y)] = cnt
    return cnt

print(DFS(0,0))

 

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

1890번: 점프

N = int(input())

maps = [ [int(x) for x in input().split()] for _ in range(N)]

move_x = [1,0]
move_y = [0,1]

def DFS(x,y,memo={}) :
    cnt = 0

    if (x,y) == (N-1,N-1) :
        ### 가장 오른쪽 밑으로 도달한 경우는 count가 됨
        cnt += 1
        return cnt
    
    ### 하지만 그 외의 경우는 count가 되지 않고 return만 해줌
    if maps[x][y] == 0 :
        return cnt
        
    if (x,y) in memo : 
        return memo[(x,y)]

    for i in range(2) :
        after_x = x+move_x[i]*maps[x][y]
        after_y = y+move_y[i]*maps[x][y]

        if after_x < 0 or after_y < 0 or after_x >= N or after_y >= N :
            continue

        cnt += DFS(after_x,after_y,memo)
        
    memo[(x,y)] = cnt
    return cnt


print(DFS(0,0))