1697번: 숨바꼭질(12분)

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

구현 아이디어 1분 구현 11분

메모리 초과

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <sstream>
#include <unordered_map>
#include <queue>

using namespace std;

// BFS.

struct Data
{
    int CurrentPosition;
    int AccTime;
    Data(int CurrentPosition, int AccTime)
    {
        this->CurrentPosition = CurrentPosition;
        this->AccTime = AccTime;
    }
};

int ConvertPosition(int CurrentPosition, int Flag)
{
    if (Flag == 0)
    {
        CurrentPosition *= 2;
    }
    else if (Flag == 1)
    {
        --CurrentPosition;
    }
    else if (Flag == 2)
    {
        ++CurrentPosition;
    }
    return CurrentPosition;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    //freopen("input.txt", "rt", stdin);

    int N{}, K{};
    cin >> N >> K;

    queue<Data> Q;
    Q.push(Data(N, 0));

    while (!Q.empty())
    {
        Data CurrentData = Q.front();
        Q.pop();

        if (CurrentData.CurrentPosition == K)
        {
            cout << CurrentData.AccTime << endl;
            break;
        }

        for (int i = 0; i < 3; ++i)
        {
            int NextPosition = ConvertPosition(CurrentData.CurrentPosition, i);
            if (NextPosition < 0 || NextPosition > 100000) continue;
            Q.push(Data(NextPosition, CurrentData.AccTime + 1));
        }
    }

    return 0;
}

---

풀이

이미 방문했던 지점을 중복으로 방문하게 되어 메모리 초과가 발생. 방지하기 위해 방문 체크 배열을 사용.

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <queue>

using namespace std;

struct Data
{
    int CurrentPosition;
    int AccTime;
    Data(int CurrentPosition, int AccTime)
    {
        this->CurrentPosition = CurrentPosition;
        this->AccTime = AccTime;
    }
};

int ConvertPosition(int CurrentPosition, int Flag)
{
    if (Flag == 0)
    {
        CurrentPosition *= 2;
    }
    else if (Flag == 1)
    {
        --CurrentPosition;
    }
    else if (Flag == 2)
    {
        ++CurrentPosition;
    }
    return CurrentPosition;
}

int Check[100001];

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    //freopen("input.txt", "rt", stdin);

    int N{}, K{};
    cin >> N >> K;

    queue<Data> Q;
    Q.push(Data(N, 0));
    Check[N] = 1;

    while (!Q.empty())
    {
        Data CurrentData = Q.front();
        Q.pop();

        if (CurrentData.CurrentPosition == K)
        {
            cout << CurrentData.AccTime << endl;
            break;
        }

        for (int i = 0; i < 3; ++i)
        {
            int NextPosition = ConvertPosition(CurrentData.CurrentPosition, i);
            if (NextPosition < 0 || NextPosition > 100000 || Check[NextPosition]) continue;
            Q.push(Data(NextPosition, CurrentData.AccTime + 1));
            Check[NextPosition] = 1;
        }
    }

    return 0;
}