글 읽기 - 숨박꼭질BFS로 해결하려는데 런타임 에러가 나옵니다.

keepyourweaponaimed 4년 전 0

안녕하세요. 런타임 에러가 자꾸 발생해서 질문드립니다.

벼열을 담아 둘 chk의 갯수도 10만개에서 1개를 더 추가해 두었고, return 같은 경우도 0으로 반환 하게 했습니다.

제가 볼 때는 배열의 범위를 초과해서 접근할 만한 것이 없다고 판단이 되는데

혹시 매의 눈으로 한번 봐주시면 감사하겠습니다.

#include<cstdio>
#include<malloc.h>
#include<vector>
#include<queue>
using namespace std;
int main(){
  int a, b;
  scanf("%d %d", &a, &b);
  int *chk = (int *)malloc(sizeof(int) * 100001);
  // int chk[100001] = {};
  // for(int i=0; i<=b; i++) chk[i] = 0;
  queue<int> q;
  q.push(a);
  chk[a] = 1;
  int res = 0;
  int tmp;
  while(1){
    int t = q.size();
    for(int i=0; i<t; i++){
       tmp = q.front();
       if(tmp-1 == b || tmp +1 == b || tmp * 2 == b){
         printf("%d", res+1);
         return 0;
       }
       if(tmp - 1 > 0){
         if(chk[tmp-1] == 0){
           q.push(tmp-1);
           chk[tmp-1]++;
         }
       }
       if(tmp + 1 > 0){
         if(chk[tmp+1] == 0){
           q.push(tmp+1);
           chk[tmp+1]++;
         }
       }
       if(tmp * 2 > 0 && chk[tmp * 2] == 0){
         q.push(tmp * 2);
         chk[tmp * 2]++;
       }
       q.pop();
    }
    res++;
  }
  free(chk);
  // printf("%d", res);
}

palilo 4년 전 1

tmp * 2가 10만을 넘어갈 수 있기 때문입니다

그러면 chk[tmp * 2]++; 에서 에러가 발생하겠죠

keepyourweaponaimed 4년 전 0

아, 그 부분을 차마 인지하지 못했습니다. 알려주셔서 감사합니다.

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

문제

문제

출처

ICPC

숨박꼭질BFS로 해결하려는데 런타임 에러가 나옵니다.

keepyourweaponaimed 4년 전 0

palilo 4년 전 1

keepyourweaponaimed 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말