[C++] 백준 14248번: 점프 점프

문제 링크

14248번: 점프 점프

문제 요약

N개의 돌로 이루어진 돌다리가 있다. 이 돌다리의 각 돌에서는 돌에 쓰인 숫자만큼 좌, 우로 이동할 수 있다. 출발점이 주어질 때, 방문할 수 있는 돌의 수를 출력해야 한다.

접근 방법

재방문 처리와 범위만 잘 해주면되는 기본적인 그래프 탐색 문제입니다.

제 경우에는 DFS를 이용해서 접근하였습니다.

코드

#include <bits/stdc++.h>

using namespace std;

const int MAX = 100001;
int n, s, val[MAX];
bool visited[MAX];

void dfs(int now)
{
	if (now < 1 || now > n)
		return;
	visited[now] = true;

	dfs(now + val[now]);
	dfs(now - val[now]);
}

int main(void)
{
	cin >> n;

	for (int i = 1; i <= n; i++)
		cin >> val[i];

	cin >> s;
	dfs(s);

	int ans = 0;
	for (int i = 1; i <= n; i++)
		if (visited[i])
			ans++;

	cout << ans;
	return 0;
}