[BOJ] 18235 : 지금 만나러 갑니다

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

---

문제해석

 1 ~ N 까지 좌표들이 있고, 오리 두마리가 A 와 B 지점에서 시작해서 하루에 한 번 점프를 해가며 이동한다. 점프를 안하는 경우는 없고,  점프 크기는 1부터 시작해서 2배씩 늘어난다. 이때, 둘이 만날 수 있는지, 만난다면 몇 일이 지나고 만나는지를 구하는 프로그램을 작성하라.

문제핵심

 1. 점프 크기가 2배씩 늘어나므로 19일에 점프크기는 262,144(2^18)가 되고 N이 최대 500,000이므로 20일부터는 의미가 없어진다. 왜냐하면 20일 부터 점프 크기가 500,000보다 크므로 점프를 하면 어차피 범위를 벗어나게 된다. 따라서, 우리는 19일까지만 시뮬레이션을 진행해보면 된다. --> 19 * O(N) 으로 처리하자.

 2. 우리는 k 일에 A 오리와 B 오리가 갈 수 있는 모든 지점을 알고 있다면, (k + 1) 일에 A 오리와 B 오리가 갈 수 있는 모든 지점을 구할 수 있다. --> 모든 지점을 저장해가면서 진행해보자.

알고리즘

 문제핵심 1, 2번에 의해서 현재 A, B 오리가 도착한 지점을 통해 다음 A, B 오리가 도착한 지점을 저장해나가며 문제를 해결할 수 있다. 메모리를 조금이라도 아끼기위해 bool 배열과 flag 기법을 이용해서 저장해나갔다.

 day 0부터 시작해서 day가 짝수라면 visited[0] 에 현재 방문한 지점들이 있고, visited[1] 에 다음에 방문할 지점들을 check 해가며 문제를 해결했다.

 1) 현재 방문한 지점들 중에 겹치는 곳이 있는지. --> 있다면 오리가 만났다!

 2) 다음에 방문한 지점을 저장할 공간을 초기화한다.

 3) 현재 지점을 토대로 다음에 방문할 지점을 계산해 저장한다.

알고리즘회고

처음에는 2개의 deque를 이용해서 현재 A 오리가 갈 수 있는 모든 지점을 저장하고, B 오리가 갈 수 있는 모든 지점을 저장하고, deque의 앞에서부터 현재 지점들을 뽑아가며 jump 를 +, jump 를 - 해서 다음 지점들을 다시 deque의 뒤로 push 했다. 당연히 deque의 push, pop 이 굉장히 많이 일어났고, 현재 지점들에서 같은 지점이 있는지 없는지 체크를 위해 2개의 deque을 2중 for문으로 순회해야되서 시간초과를 맛보게 되었다. 따라서, 메모리를 조금 더 사용하고 deque을 사용하지 않는 방식으로 알고리즘을 갈아엎었다.

#include<iostream>
#include<qcueue>
#include<vector>
 
using namespace std;
int N, A, B, jump = 1, day = 0;
bool visitedA[2][500001] = {};
bool visitedB[2][500001] = {};
int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
 
    // 19일 안에 만나야됨!
 
    cin >> N >> A >> B;
 
    visitedA[0][A] = 1;
    visitedB[0][B] = 1;
    do {
        // day 가 짝수라면 visited[0] 에 기존것이있음!
        // day 가 홀수라면 visited[1] 에 기존것이있음!
        int today = day % 2;
        int nextDay = (today + 1) % 2;
        // 같은게 있는지 찾아보자.
        bool flag = false;
        for (int i = 1; i <= N; i++) {
            if (visitedA[today][i] && visitedB[today][i]) {
                flag = true;
                break;
            }
        }
        if (flag) {
            cout << day << '\n';
            break;
        }
 
        // 초기화 진행
        for (int i = 1; i <= N; i++){
            visitedA[nextDay][i] = 0;
            visitedB[nextDay][i] = 0;
        }
        for (int i = 1; i <= N; i++) {
            int nextJump1 = i + jump, nextJump2 = i - jump;
            if (visitedA[today][i]) {
                if (1 <= nextJump1 && nextJump1 <= N) visitedA[nextDay][nextJump1] = 1;
                if (1 <= nextJump2 && nextJump2 <= N) visitedA[nextDay][nextJump2] = 1;
            }
            if (visitedB[today][i]) {
                if (1 <= nextJump1 && nextJump1 <= N) visitedB[nextDay][nextJump1] = 1;
                if (1 <= nextJump2 && nextJump2 <= N) visitedB[nextDay][nextJump2] = 1;
            }
        }
        jump *= 2;
        day++;
    } while (jump <= 500000);
    if (jump > 500000) cout << -1;
    return 0;
}

---