[C++] BOJ 18235 지금 만나러 갑니다 (배열의 초기화 정리)

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

[English Translation]

On the way returning to their home country "Quack Quack Land" , Duck and Buck (Author's translation: duck is 'ori' in korean language, and the syllable 'o' means number 5, and this problem decided to call a different duck yuk-ri, which literally translates into 6-ri, since 'yuk' is 6 in korean. just a word pun, and I just decided to call an other duck an 'Buck.') lost their way home. As of right now, Duck is at point A, and Buck is at point B.

Duck and Buck must have jump once per day, to find each other. On the first day, they jump by 1 unit, and each day, they want to meet each other more, so they jump twice further from the day before. So, if their position is X and it's their y-th day, they can jump to either point X+2^(y-1) or to point x-2^(y-1). If they try to jump to a position smaller than 0 or greater than n+1, they cannot meet eternally.

The diagram below shows an example when N = 10, A = 4, and B = 10. The arrows indicate the possible jump positions.

When the positions of Duck and Buck are given, find the minimum number of days it takes for them to meet. Duck and Buck are considered to have met if they land on the same point on the same day.

[Input]

The first line contains three integers, N,A, and B.

[Output]

Print the minimum number of days, that it takes for a Duck and a Buck to meet.

#include <iostream>
#include <algorithm>
#include <queue>
#include <memory.h>
#include <cmath>
using namespace std;

int map[500001];
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n,a,b;
    cin>>n>>a>>b;
    int answer=-1;
    queue <pair<int,int>> q;
    q.push({a,0});
    q.push({b,0});
    while (!q.empty()){
        int loc=q.front().first;
        int day=q.front().second;
        q.pop();
        int dist=pow(2,day);
        int next=loc+dist;
        if (next<=n){
            if (map[next]==day+1){
                answer=day+1;
                break;
            }
            else{
                map[next]=day+1;
                q.push({next,day+1});
            }
        }
        next=loc-dist;
        if (next>0){
            if (map[next]==day+1){
                answer=day+1;
                break;
            }
            else{
                map[next]=day+1;
                q.push({next,day+1});
            }
        }
    }
    cout<<answer;
    return 0;
}

map은 제일 최근에 방문을 했을 때의 좌표이다.

서로 오리와 육리가 만날 수 없을 때 -1을 출력해야 하므로 answer에 -1을 default로 부여했고,

queue를 통해 오리와 육리를 (좌표, day)를 기준으로 저장했다.

여기서 조심해야하는 부분은 도착했던 좌표를 다른 day에서 올 수 있다는 점이다.

예컨대, 3에서 2로 간다고 해보자.

3->2로 하루만에 갈 수도 있고,

3->4->2와 같이 이틀을 거쳐서 갈 수 있다. 그렇기에 과거 도착을 했던 기록이 있는 여부를 저장하는 것이 아닌, 최근에 도착했던 일수를 저장하는 map을 이용하였다.

하지만 각각 오리나 육리가 두 개 이상의 방법으로, 같은 날에 같은 장소를 도착하는 방법은 존재하지 않는다.

즉, 3->2으로 이동한다고 할 때, 3->4->2로 가는 방법은 이틀 안에 도착 한다는 것이 유일하다는 것이다.

따라서 따로 오리와 육리를 다른 queue에 저장하지 않고, 같은 queue를 사용하여, 이미 map[위치]= 현재날짜라면, 이미 오리가 육리가 오기 전에 해당 일자에 방문했다는 의미와 같다.

또한, 배열을 main 함수 내에 저장하고 제출을 했는데, 반복적으로 '틀렸습니다'를 받았다.
이는 배열에 쓰레기값이 들어가서였다.
memset을 이용하거나, 배열을 global하게 선언하니 정답을 받았다.

C++에서는 배열을 선언할 때,

글로벌하게 변수를 선언할 경우: 자동으로 배열 내에 0으로 채워지게 된다.

함수 내에 변수를 선언할 경우: 초기화하지 않으면 쓰레기값으로 채워진다. memset이나 for 문을 이용하여 초기화하자.