[백준 11048번 / C++] 이동하기

dp와 dfs를 활용한 문제이다.

이와 비슷한 문제를 아래에 dp 카테고리에 추가한 적이 있어서 이번엔 dfs 카테고리에 집어넣겠다. 

[백준 1520번 / C++] 내리막 길

---

dfs와 dp를 결합한 문제를 설명하기 위에 아래와 같은 예시를 들겠다. 

 

어떤 착한 조상이 dfs라는 배를 타고 여행을 떠나는데 길을 잘 모르는 상태이다. 그래서 현재 위치(X)를 표시해주고 그 위치에서 갈 수 있는 "A,B,C"의 3개의 갈림길을 "A"부터 차례대로 여행을 계속한다. 결국 가고자하는 도착지점에 도착했을 때 아까 체크해주었던 현재 위치(X)로 돌아가고 "B"라는 갈림길로 또 여행을 간다. "C"까지 여행을 다하고 나서 현재 위치(X) 로 돌아온다. 그리고 현재 위치(X)에 "A,B,C"로 가는 길 중 최대인 비용을 현재 위치(X)에 저장해준다. 

 

이후 젊은 여행자들이 현재 위치(X)에 도착했을 때 착한 조상이 새겨놓은 최대비용을 보고 현재위치에서 도착지점까지 갈 수 있는 최대비용은 이 값이구나 아는 것이다. 

 

이게 DP 메모이제이션이라는 것이다.

#접근방법

1. 아래, 오른쪽, 대각선 방향으로 dfs 호출 
2. 맵을 초과하면 continue
3. 도착지점에 도착했으면 마지막 사탕 개수 리턴
4. cost라는 dp 배열에 최대 사탕 개수를 저장해놓는다. 

#include <iostream>
#include <algorithm>
using namespace std;
int map[1001][1001]; 
int m, n; 
int cost[1001][1001]; 
int dx[3] = { 0,1,1 }; 
int dy[3] = { 1,0,1 }; 

int dfs(int y, int x) {
    if (y == m-1 && x == n-1) return map[y][x];          
    int& res = cost[y][x]; 
    if (res!=-1)return res; 
    res = 0; 
    for (int i = 0; i < 3; i++) {
        int nx = dx[i] + x; 
        int ny = dy[i] + y;
        if (nx < 0 || nx >= n || ny < 0 || ny >= m)continue;  
        res=max(dfs(ny, nx)+map[y][x],res);     
    }
    return res; 
}

int main()
{    
    cin >> m >> n; 
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            cin >> map[i][j]; 
            cost[i][j] = -1; 
        }
    }
    cout<<dfs(0, 0);
}

 

11048번: 이동하기