[백준 14248번] 점프 점프 (C++)

문제링크 : https://www.acmicpc.net/problem/14248

14248번: 점프 점프

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAX = 987654321;

int N, result, s;
int arr[100001];
bool visited[100001];

void dfs(int cur)
{
    if(cur<1 || cur>N) return; //범위 조건
    visited[cur] = 1;
    dfs(cur+arr[cur]); //앞으로
    dfs(cur-arr[cur]); //뒤로
}

int main()
{
    ios_base::sync_with_stdio(0); 
	cin.tie(0);
    
    cin >> N;
    for(int i=1; i<=N; i++) cin >> arr[i];
    cin >> s;
    dfs(s);
    for(int i=1; i<=N; i++) if(visited[i]) result++; //방문체크

    cout << result;
    return 0;
}

 

나름 간단한 dfs 문제이다.

입력받은 시작점을 기준으로 dfs를 돌려주며, 이동하는 방향이 앞과 뒤이므로 해당 2개에 대해서 재귀를 다시 돌려준다.

앞으로 가는 것은 현재 위치 + 점프 가능 횟수, 뒤로 가는 것은 현재 위치 - 점프 가능 횟수로 값을 넣어준다.

 

범위조건이자 종료조건으로 현재 위치가 1보다 작거나 N을 넘어서면 종료하도록 해준다.

재귀를 도는 모든 값에 대해 방문처리를 해주고, 나중에 이 방문처리된 가짓수를 세어주면 이것이 구하고자하는 정답이다.