[백준/Baekjoon] 1326 폴짝폴짝 C++ :: Graph & BFS

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

1326번: 폴짝폴짝

---

1. Logic

처음에 DP로 될거같아서 시도했는데 DP는 vis배열을 찍고 나오기 때문에 최단거리 계산이 안된다. 그리고 vis배열을 기록을 안하게 되면 루프를 계속 들어가기 때문에 힙이 터진다..ㅋㅋㅋㅋ

결국 BFS 느낌으로 해결

 

이 문제에서 " 징검다리에 쓰여 있는 수의 배수만큼 떨어져 있는 곳으로만 갈 수 있다."는 배수만큼 앞으로 이동 + 배수만큼 뒤로 이동할 수 있다.

---

2. Code

#include <bits/stdc++.h>

using namespace std;

int dist[10001];
int cnt[10001];
bool vis[10001];

int n;
int s, e;

void solve() {
    queue<int> q;
    q.push(s);
    vis[s] = true;
    
    while(!q.empty()) {
        int cur = q.front();
        q.pop();
        
        if(cur == e) return;
        
        for(int i = cur + dist[cur]; i <= n; i += dist[cur]) {
            if(vis[i]) continue;
            vis[i] = true;
            cnt[i] = cnt[cur] + 1;
            q.push(i);
        }
        
        for(int i = cur - dist[cur]; i >= 1; i -= dist[cur]) {
            if(vis[i]) continue;
            vis[i] = true;
            cnt[i] = cnt[cur] + 1;
            q.push(i);
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

    cin >> n;
    
    for(int i = 1; i <= n; i++) {
        cin >> dist[i];
    }
    
    cin >> s >> e;

    solve();
    
    if(cnt[e] == 0) cout << -1;
    else cout << cnt[e];
}

알고리즘 Solve 후 제가 생각한 Logic을 기록하는 개인 공부 블로그입니다.
내용 중 최적화가 가능한 부분등은 언제든지 댓글로 틀린 부분 및 피드백 주시면 공부 및 반영하겠습니다🧐