[백준][DP] 1890번 점프

문제

제일 왼쪽 위칸에서 제일 오른쪽 아래칸까지 갈 수 있는 경로의 수를 구해야한다. 각 칸에는 점프할 수 있는 거리가 적혀져있고 오른쪽 또는 아래쪽으로만 점프할 수 있다.

문제출처: 백준 온라인 저지(https://www.acmicpc.net/problem/1890)

풀이

처음에는 BFS로 접근했었다. 첫 칸을 큐에 넣어준다음 while문을 통해서 큐에 값을 빼내고 해당하는 위치에서 갈 수 있는 칸들을 큐에 넣도록 했다. 처음엔 모두 큐에 넣어버리고 (0, 0)을 시작으로 했을 때 (N-1, N-1)이 큐에서 나오면 카운트를 해주도록 했다. 그렇게 했더니 큐에 너무나 많은 경로들이 들어가서 메모리 초과가 났다. 메모리 초과를 해결하기 위해서 visited배열을 만들었고, 만약 이미 해당하는 칸에 이미 갔었다면 큐에 넣지 않고 visited 배열에서 해당 경로에 올 수 있었던 경로의 수를 축적해줬다. 약간 여기서 dp의 개념이 필요하다 생각하고 제출했지만 틀렸습니다였다! 문제는 큐에서 나오는 순서의 문제였는데 넣은 순서대로 빼면서 오른쪽, 아래쪽으로 새로운 경로들을 넣어주다보니 만약 (3, 3)에서 오른쪽으로 점프를 하면서 dp[3][3]의 값을 그 다음 칸의 dp값으로 더해주었는데 큐에서 계속 값이 나오다가 (3, 3)로 오는 경로가 또 생기는 경우가 있을 수 있다. dp[3][3]의 값이 완전히 정해지고 그 다음칸으로 저 값이 더해져야하는데 그렇지 않은 경우가 있다는 것이다. 큐에서 나오는 순서에 규칙이 없기 때문에 dp값이 엉망이 되어버리는 문제가 있었다. 그래서 while문에서 BFS의 모습을 유지하며 구현해보려했으나 순서를 맞추기 위해 원래 dp풀듯이 고쳐풀었다. 첫 칸에서부터 오른쪽으로 시작하며 아래쪽으로 내려오며 dp 값을 채워주니 맞았다. 아! 그리고 최대 경로의 수가 크기 때문에 int로는 부족해서 long long 타입으로 해주어야 한다.

코드

#include<iostream>

#include<queue>

using namespace std;

int map[101][101];

long long visited[101][101];

int main(){

int N;

cin>>N;

for(int i=0; i<N; i++){

for(int j=0; j<N; j++)

cin>>map[i][j];

}

visited[0][0] = 1;

for(int i=0; i<N; i++){

for(int j=0; j<N; j++){

if(map[i][j] == 0)

continue;

if(i+map[i][j] < N)

visited[i+map[i][j]][j] += visited[i][j];

if(j+map[i][j] < N)

visited[i][j+map[i][j]] += visited[i][j];

}

}

cout<<visited[N-1][N-1]<<endl;

return 0;

}