[ 백준 11060 ] 점프 점프 (C++)

백준의 점프점프(11060) 문제이다.

[ 문제 바로가기 ]

[ 문제풀이 ]

1) 본인은 이 문제를 2가지 방법으로 접근해 보았다.

   첫 번째 방법은 단순 너비우선탐색(BFS)으로 구현해 보았다.

   배열의 Index번호와, 움직인 횟수를 Queue에서 관리하도록 만들어서, 현재 인덱스에서 갈 수 있는 모든 칸을 가보면서

   탐색을 진행했다.

   두 번째 방법은 메모이제이션을 이용해서 DFS + DP로 구현해 보았다.

   현재 노드에서 갈 수 있는 모든 칸들을 재귀로 호출하면서 탐색을 진행할 때, 이미 기존에 탐색한 적이 있던 노드라면

   저장되어 있는 노드의 경로의 갯수를 그대로 가져와서 사용하는 방식을 이용했다.

  

[ BFS풀이 소스코드 ]

#include<iostream>
#include<queue>
 
#define endl "\n"
#define MAX 1000
using namespace std;
 
int N;
int Arr[MAX];
bool Visit[MAX];
 
void Input()
{
    cin >> N;
    for (int i = 0; i < N; i++) cin >> Arr[i];
}
 
void Solution()
{
    queue <pair<int, int>> Q;
    Q.push(make_pair(0, 0));
    Visit[0] = true;
 
    while (Q.empty() == 0)
    {
        int Cur = Q.front().first;
        int Cnt = Q.front().second;
        Q.pop();
 
        if (Cur == N - 1)
        {
            cout << Cnt << endl;
            return;
        }
 
        int S = Arr[Cur];
        for (int i = 1; i <= S; i++)
        {
            int Next = Cur + i;
            if (Visit[Next] == false)
            {
                Visit[Next] = true;
                Q.push(make_pair(Next, Cnt + 1));
            }
        }
    }
    cout << -1 << endl;
}
 
void Solve()
{
    Input();
    Solution();
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}

[ DFS + DP 소스코드 ]

#include<iostream>
#include<cstring>
 
#define endl "\n"
#define MAX 1000
#define INF 987654321
using namespace std;
 
int N;
int Arr[MAX];
int DP[MAX];
 
int Min(int A, int B) { if (A < B) return A; return B; }
 
void Input()
{
    cin >> N;
    for (int i = 0; i < N; i++)
    {
        cin >> Arr[i];
    }
}
 
int DFS(int Cur)
{
    if (Cur >= N) return INF;
    if (Cur == N - 1) return 0;
    if (DP[Cur] != -1) return DP[Cur];
 
    DP[Cur] = INF;
    for (int i = 1; i <= Arr[Cur]; i++) DP[Cur] = Min(DP[Cur], DFS(Cur + i) + 1);
    
    return DP[Cur];
}
 
void Solution()
{
    memset(DP, -1, sizeof(DP));
    int Answer = DFS(0);
    if (Answer == INF) cout << -1 << endl;
    else cout << Answer << endl;
}
 
void Solve()
{
    Input();
    Solution();
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}