글 읽기 - 숨바꼭질 4 질문드립니다.

zhh1020 4년 전 0

2배로 이동할 경우를 고려해 visit을 최대크기의 2배로 주고

-1, +1, *2값을 BFS로 돌려주었는데 틀려서 질문드립니다..

반례부탁드려요

질문게시판 다 확인했습니다 ㅠㅠ

#include <iostream>
#include <queue>
using namespace std;

int n, k;
int visit[200002];
int dir[2] = {-1, 1};

queue<int> que;
vector<int> ans;
int time_;

int inside(int x)
{
    return x >= 0 && x <= 200002;
}

void calc()
{
    int value = k;
    ans.push_back(value);
    while (value != n)
    {
        ans.push_back(visit[value]);
        value = visit[value];
    }
}

void BFS()
{

    que.push(n);
    visit[n] = n;

    while (!que.empty())
    {
        int SIZE = que.size();
        for (int i = 0; i < SIZE; i++)
        {
            int cur = que.front();
            que.pop();
            if (cur == k)
            {
                calc();
                return;
            }
            for (int j = 0; j < 2; j++)
            {
                int next = cur + dir[j];
                if (inside(next) && visit[next] == -1)
                {
                    visit[next] = cur;
                    que.push(next);
                }
            }
            int next = cur * 2;
            if (inside(next) && visit[next] == -1)
            {
                visit[next] = cur;
                que.push(next);
            }
        }
        time_++;
    }
}

int main(void)
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> n >> k;
    for (int i = 0; i <= 200002; i++)
        visit[i] = -1;
    BFS();
    cout << time_ << "\n";
    while (!ans.empty())
    {
        cout << ans.back() << " ";
        ans.pop_back();
    }
}

zhh1020 4년 전 0

자답입니다.

배열 크기를 잡아주고 범위를 벗어난 부분에 값을 넣어서 생긴 문제였습니다.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

숨바꼭질 4 질문드립니다.

zhh1020 4년 전 0

zhh1020 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말