[백준 1326 C++][S2] 폴짝폴짝

⭐️ 난이도

Silver 2

---

⭐️ 문제

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

1326번: 폴짝폴짝

 

---

⭐️ Idea flow

문제를 간단하게 정리해보자.

1. 징검다리는 1번부터 n번까지 있다.
2. 현재 칸에서 각 징검 다리에 쓰여 있는 숫자의 배수만큼 떨어진 곳에만 갈 수 있다.
3. a번 다리에서 b번 다리로 이동하려고 할 때, 최소 이동 횟수는 몇 번인지 구하시오.

 

시작점과 도착점이 주어지고, 시작점에서 도착점까지 이동하는 최소 이동 횟수를 구하는 것이기 때문에 BFS를 사용한다.

이 문제에서 가장 중요한 컨셉은 "징검다리에 쓰여 있는 수의 배수만큼 떨어진 곳"에 이동이 가능하다는 것이다.

전형적인 BFS 문제인 것 같지만 신경써야 할 포인트가 있다.

 

이동을 오른쪽(양의 방향)과 왼쪽(음의 방향) 모두 이동할 수 있다는 점이다. 

문제에서 쓰여 있는 수의 배수만큼 떨어진 곳에 이동이 가능하다고 했기 때문에 음의 방향으로도 이동을 할 수 있다.

따라서 현재 위치에서 반복문을 두 번 실행하여 양의 방향과 음의 방향 모두 확인해주어야 한다.

 

각 징검다리마다 적혀있는 정수를 vector 컨테이너에 저장해놓고, 현재 징검다리에 적혀있는 번호를 인덱스를 통해 불러온다.

그리고 이를 interval이라는 변수에 담아둔다.

 

양의 방향으로 진행하는 것을 생각해보자.

현재 위치에서 징검다리에 적혀있는 숫자의 배수들을 더한 곳에 갈 수 있다.

또한 징검다리가 n개 있기 때문에, 징검다리에 적혀있는 숫자의 배수를 더한 값이 n보다 작거나 같을 때까지 반복하면 된다.

// 오른쪽으로 진행하는 방법
for(int i = 1; cur + (interval * i) <= n; ++i){
    int next = cur + (interval * i);
    if(!isVisited[next]){
        isVisited[next] = true;
        q.push({next, time + 1});
    }
}

 

음의 방향으로 진행하는 것을 생각해보자.

현재 위치에서 징검다리에 적혀있는 숫자의 배수들을 뺀 곳에 갈 수 있다.

징검다리는 1번이 제일 작은 번호이기 때문에, 징검다리에 적혀있는 숫자의 배수를 뺀 값이 1보다 크거나 같을 때까지 반복하면 된다.

// 왼쪽으로 진행하는 방법
for(int i = 1; cur - (interval * i) >= 1; ++i){
    int next = cur - (interval * i);
    if(!isVisited[next]){
        isVisited[next] = true;
        q.push({next, time + 1});
    }
}

 

 

---

⭐️ Code

#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
#include <cmath>
#include <vector>
#include <queue>

#define INF 10000000000000
using namespace std;

// 1326 - 폴짝폴짝
int n;
int a, b, result = -1;
vector<int> bridge, isVisited;


void input(){
    cin >> n;
    bridge.assign(n + 1, 0);
    isVisited.assign(n + 1, false);
    for(int i = 1; i <= n; ++i){
        cin >> bridge[i];
    }
    cin >> a >> b;
}

void BFS(int a){
    queue<pair<int, int>> q;
    q.push({a, 0});
    isVisited[a] = true;

    while(!q.empty()){
        int cur = q.front().first;
        int time = q.front().second;
        int interval = bridge[cur];
        q.pop();

        if(cur == b){
            result = time;
            return;
        }

        // 오른쪽으로 진행하는 방법
        for(int i = 1; cur + (interval * i) <= n; ++i){
            int next = cur + (interval * i);
            if(!isVisited[next]){
                isVisited[next] = true;
                q.push({next, time + 1});
            }
        }
        // 왼쪽으로 진행하는 방법
        for(int i = 1; cur - (interval * i) >= 1; ++i){
            int next = cur - (interval * i);
            if(!isVisited[next]){
                isVisited[next] = true;
                q.push({next, time + 1});
            }
        }
    }
}

void solve(){
    BFS(a);
    cout << result;
}

int main(){

    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    input();
    solve();

    return 0;
}

 

---

⭐️ Feedback

문제를 읽고 처음 풀었을 때에는 무심코 양의 방향으로만 진행이 가능하다고 생각했다.

하지만 배수만큼 떨어진 곳!에 갈 수 있는 것이기 때문에 음의 방향으로도 진행이 가능한 상황이었다.

문제를 좀 더 자세히 읽고 조건을 제대로 파악하는 습관을 들이자!