[백준 1326번] 폴짝폴짝 (C++)

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

1326번: 폴짝폴짝

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

int N, a, b, result=-1;
int arr[100001];
int visited[100001];

void bfs(int s)
{
    queue<pii>q;
    q.push({a, 0}); //시작점, 점프횟수
    visited[a]=1;

    while(!q.empty())
    {
        auto [cur, cnt] = q.front();
        q.pop();

        if(cur==b) 
        {
            result=cnt; 
            return; //목표 지점 도달
        }

        for(int i=1; cur + (arr[cur]*i) <=N; i++) //앞으로 점프
        {
            int next = cur + (arr[cur]*i);
            if(visited[next]) continue;
            visited[next]=1;
            q.push({next, cnt+1});
        }

        for(int i=1; cur - (arr[cur]*i) >=1; i++) //뒤로 점프
        {
            int next = cur - (arr[cur]*i);
            if(visited[next]) continue;
            visited[next]=1;
            q.push({next, cnt+1});
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(0); 
	cin.tie(0);
    
    cin >> N;
    for(int i=1; i<=N; i++) cin >> arr[i];
    cin >> a >> b;
    bfs(a);
    cout << result;
    return 0;
}

 

bfs의 응용문제이다.

큐에 시작점인 a와 점프횟수인 0을 넣고 시작한다.

 

이제 반복문들 돌려서 점프를 시작한다.

현재 위치 cur에 arr[cur]*i값을 더해주어 arr[cur]의 배수만큼 점프하도록 해준다.

따라서 다음위치의 값은 cur + arr[cur]*i이다.

중복체크를 위해 해당값을 방문처리해주고, 큐에 해당값과 점프횟수 + 1를 해주고 넘겨준다.

 

여기서 주의해야할 것은 점프가 앞으로만 가능한 것이 아니라는 것이다.

뒤로도 점프가 가능하기 때문에 (ex 5->1) 이에 대한 것도 반복문을 작성해주어야 한다.

현 위치 cur에서 이번엔 뒤로 가기 때문에 arr[cur]*i의 값을 빼주면 된다.

 

이렇게 큐에 들어간 next의 값이 목표값인 b에 도달하면 result에 여태 누적한 cnt를 저장하고 출력해주면 된다.

 

추가적으로 주의해야할 것은 도달하지 못한 경우 -1을 출력해야하는 것이다.

나또한 이를 주의하지 못하여 여러번 틀리다가 늦게 알아챘는데 이를 위해 결과값을 담을 result의 초기값을 -1로 설정해주어야한다.