글 읽기 - OutofBound 이유를 모르겠습니다...

nicolao00 2년 전 0

17,18번에 n1과 n2의 맥스값을 넣지않으면 outofBound 오류가 뜨더라구요 근데 그 이유을 모르겠어요.. 이 코드들에서 outofBound 뜰만한 곳이

또 있나요? 요즘 bfs 구현하면서 outofBound때문에 계속 애먹고있는데 이유를 도저히 모르겠네요 ㅠㅠ

vector에 추가할 값의 최대범위를 정해주지않았다해도 한정된 vector의 용량을 초과하기 전에 무조건 반복문이 종료되지않나요..?

#include <iostream>
#include <vector>
#include <queue>
#define MAX 100001
using namespace std;
queue<int> que;
vector<int> v[2*MAX];
int visited[2*MAX];

void bfs(int s,int e){
    v[0].push_back(s); int ans=1; visited[s]=1; que.push(s);
    
    while(1){
        while(!que.empty()){
            int num=que.front(); int n1=num-1, n2=num*2;
            if(n1==e||n2==e) {cout<<ans; return;}           
            if(0<=n1&&n1<=2*MAX&&!visited[n1]) {v[ans].push_back(n1); visited[n1]=1;}
            if(0<=n2&&n2<=2*MAX&&!visited[n2]) {v[ans].push_back(n2); visited[n2]=1;}
            que.pop();
        }
        
        for(int i=0;i<v[ans].size();i++)
            que.push(v[ans][i]);
        ans++;
    }
}

int main(){
    int start,end; cin>>start>>end;
    if(start==end) cout<<"0";
    bfs(start,end);
}

bupjae 2년 전 0

int visited[2*MAX]; 라고 선언하면 [0] ~ [2*MAX-1] 까지의 공간을 사용할 수 있습니다.

하지만 이 코드는 [2*MAX] 번째 공간을 사용하고 있습니다.

nicolao00 2년 전 0

@bupjae

아래 코드는 수정해서 정답이 나온 코드인데 이건 outofbound가 나오지않고 정답이라고 나왔는데

말씀하신 부분대로라면 아래코드도 [2*MAX] 공간을 사용하니까 outofBound 나와야하는거 아닌가요??

#include <iostream>
#include <vector>
#include <queue>
#define MAX 100001
using namespace std;
queue<int> que;
vector<int> v[2*MAX];
int visited[2*MAX];

void bfs(int s,int e){
    v[0].push_back(s); int ans=1; visited[s]=1; que.push(s);
    
    while(1){
        while(!que.empty()){
            int num=que.front(); int n1=num-1, n2=num*2, n3=num+1;
            if(n1==e||n2==e||n3==e) {cout<<ans; return;}           
            if(0<=n1&&n1<=2*MAX&&!visited[n1]) {v[ans].push_back(n1); visited[n1]=1;}
            if(0<=n2&&n2<=2*MAX&&!visited[n2]) {v[ans].push_back(n2); visited[n2]=1;}
            if(0<=n3&&n3<=2*MAX&&!visited[n3]) {v[ans].push_back(n3); visited[n3]=1;}
            que.pop(); //ans 올려줘야함
        }
        
        for(int i=0;i<v[ans].size();i++)
            que.push(v[ans][i]);
        ans++;
    }
}

int main(){
    int start,end; cin>>start>>end;
    if(start==end) {cout<<"0"; return 0;}
    bfs(start,end);
}

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

문제

문제

출처

ICPC

OutofBound 이유를 모르겠습니다...

nicolao00 2년 전 0

bupjae 2년 전 0

nicolao00 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말