(C++) - 백준(BOJ) 14248 : 점프 점프

https://www.acmicpc.net/problem/14248

14248번: 점프 점프

bfs 문제였습니다.

📕 풀이방법

📔 입력 및 초기화

돌 개수 n, 돌당 써져 있는 숫자 stone, 방문 여부를 저장할 ck, 시작 점 s, 정답 ans를 선언한 후 적절히 입력받습니다.

📔 풀이과정

어떤 정점에서 시작해도 방문가능한 모든 돌을 방문할 수 있는 알고리즘 중 하나인 bfs를 수행합니다.

1. 현재 돌의 지점을 x라 하면 다음 방문 가능한 돌은 x-stone[x] 또는 x+stone[x]입니다. 범위를 넘지 않는 다면 방문 가능하므로 queue에 다음 지점으로 push해줍니다. 방문여부를 check해줍니다.

ck배열을 모두 확인하며 방문했다면 ans++해줍니다.

📔 정답출력

ans를 출력해줍니다.

---

📕 Code

#include <bits/stdc++.h>
using namespace std;
int n, stone[100001], ck[100001], s, ans;

void bfs(){
  ck[s] = 1;
  queue <int> q;
  q.push(s);

  while(!q.empty()){
    int x = q.front();
    q.pop();
    
    if(1 <= x - stone[x] && !ck[x - stone[x]]) {
      ck[x - stone[x]] = 1;
      q.push(x - stone[x]);
    }

    if(x + stone[x] <= n && !ck[x + stone[x]]) {
      ck[x + stone[x]] = 1;
      q.push(x + stone[x]);
    }
  }
}

int main(){
  cin >> n;
  for(int i = 1; i <= n; i++) cin >> stone[i];
  cin >> s;
  bfs();
  for(int i = 1; i <= n; i++) 
    if(ck[i]) 
      ans++;
  cout << ans;
}

---

*더 나은 내용을 위한 지적, 조언은 언제나 환영합니다.