[백준 18235] 지금 만나러 갑니다 (C++)

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

18235번: 지금 만나러 갑니다

1. 주의할 점

- 구간은 [1,len]이다

- 같은 점을 다른 Day에 방문할 수 있다

Ex)
구간: [1,10]
시작위치: 5
목표위치: 4

방법1: 5 → 4
방법2: 5 → 6 → 4
방법3: 5 → 6 → 8 → 4

각 방법으로 5→4로 갈 수 있는 날은 1,2,3일에 모두 도달 가능

 

2. 구현

- Arr[] 배열을 통해 해당 위치에 방문한 날을 적는다

- Info 구조체를 이용하여 현재 위치, 날, 점프 거리를 담는다

- Queue를 통해 BFS를 수행하여 현 위치를 기준으로 좌우 방향으로 움직였을 때, 같은 날 움직여서 도착할 수 있는 곳이 있다면 종료한다

 

#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
struct info{
    int curLoc,day,jump;
};
int arr[500001];

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    int len,a,b,result=-1;
    cin>>len>>a>>b;
    queue<info> q;
    q.push({a,0,0});
    q.push({b,0,0});
    while(!q.empty()){
        int cc = q.front().curLoc;
        int cd = q.front().day;
        int cj = q.front().jump;
        q.pop();
        int dist = cj==0?1 : cj*2;
        int next = cc+dist;
        if(next<=len){        //우측 이동
            if(arr[next]==cd+1){
                result=cd+1;
                break;
            }
            else{
                arr[next]=cd+1;
                q.push({next,cd+1,dist});
            }
        }
        next = cc-dist;
        if(next>0){        //좌측 이동
            if(arr[next]==cd+1){
                result=cd+1;
                break;
            }
            else{
                arr[next]=cd+1;
                q.push({next,cd+1,dist});
            }
        }
    }
    cout<<result;
    return 0;
}