글 읽기 - 런타임에러를 해결할 수 없습니다.. 도움부탁드립니다.

cheng1230 4년 전 0

범위값이 문제인건지 여기저기 다 고쳐봐도 도저히 해결이 안되네요.. 도움부탁드립니다.

#include <iostream>
#include <queue>

using namespace std;

int arr[100005] = { 0 };

void bfs(int N, int K) {

	queue<int> q;
	q.push(N);
	int tmp;

	while (!q.empty()) {

		tmp = q.front();
		q.pop();

		if (tmp == K) break;
		else {
			if (arr[tmp * 2] == 0 && tmp * 2 <= 100001) {
				arr[tmp * 2] = arr[tmp] + 1;
				q.push(tmp * 2);
			}
			if (arr[tmp - 1] == 0 && tmp - 1 >= 1 && tmp - 1 <= 100001) {
				arr[tmp - 1] = arr[tmp] + 1;
				q.push(tmp - 1);
			}
			if (arr[tmp + 1] == 0 && tmp + 1 <= 100001) {
				arr[tmp + 1] = arr[tmp] + 1;
				q.push(tmp + 1);
			}
		}


	}
}
int main() {

	int N, K;

	cin >> N >> K;
	if (N < K) {
		bfs(N, K);
		cout << arr[K];
	}
	else if (N == K) cout << 0;
	else cout << N - K;

}

wjddydgns99 4년 전 1

중복 방문하면 큐안에 들어갈 수 있는 최대치를 초과할 수 있겠죠?

minjoonist 4년 전 1

bool visited[]={} 배열을 만들어서 한번 방문했으면 visited[i]를 true로 해주고

if(!visited[i])이면 bfs queue에 넣게 하면 됨니다.

cheng1230 4년 전 0

중복 방문을 체크하기 위해 arr배열을 0으로 초기화하고 if문에서 0일떄만 q에 추가 되도록 하였습니다.

저 방법이 문제인걸까요 ?

minjoonist 4년 전 1

음 이걸 설명하려면 and연산자의 특징을 알아야 하는데(&&)

and연산자는 왼쪽부터 계산한다음 왼쪽이 true일 경우 오른쪽까지 비교합니다. 왼쪽이 false이면 바로 오른쪽을 비교하지 않고 끝네버리죠.

21 25 29줄에서 각각

arr[tmp*2], arr[tmp+1], arr[tmp-1]을 비교합니다. 그다음에tmp의 값이 10000001보다 작은지

검사하므로 이미 tmp*2가 이미 1000001 을 넘어갔는데 and 연산자에서 왼쪽인 arr[tmp*2]를 하므로 런타임 에러가 나는것 같습니다.

해결책은 그냥 visited배열을 쓰던가(이 방법을 가장 추천합니다. 가독성도 좋고 런타임 에러가 잘 안남니다.)

21 25줄에서 먼저 tmp의 범위를 검사하시게 하면 됨니다. if(tmp*2<=1000001 && ...)

wjddydgns99 4년 전 1

1. 0으로 초기화하면 문제점이 arr[N]은 시작점으로 방문했음에도 불구하고 나중에 재방문합니다.

2. void함수 안에 리턴이 없습니다. 이는 런타임에러를 유발할 수 있습니다.

3. int arr[10]이란 배열이 있습니다. index=11이에요.

if(arr[index]==0 && index<=10) 과 if(index<=10 && arr[index]==0)은 같을까요?

런타임 에러 원인 링크 첨부합니다.

https://www.acmicpc.net/board/view/22980

cheng1230 4년 전 0

댓글 감사드립니다. .말씀해주신 부분들을 보고 큰 도움이 되어 런타임문제를 해결하였습니다..

그런데 틀렸습니다가 나오는데 반례를 찾지못하겠습니다.

#include <iostream>
#include <queue>

using namespace std;

int arr[100005] = { 0 };

void bfs(int N, int K) {

	queue<int> q;
	q.push(N);
	int tmp;

	while (!q.empty()) {

		tmp = q.front();
		q.pop();

		if (tmp == K) break;
		else {
			if (tmp * 2 <= 100001 && arr[tmp * 2] == 0) {
				arr[tmp * 2] = arr[tmp] + 1;
				q.push(tmp * 2);
			}
			if (tmp - 1 >= 1 && tmp - 1 <= 100001 && arr[tmp - 1] == 0) {
				arr[tmp - 1] = arr[tmp] + 1;
				q.push(tmp - 1);
			}
			if (tmp + 1 <= 100001 && arr[tmp + 1] == 0) {
				arr[tmp + 1] = arr[tmp] + 1;
				q.push(tmp + 1);
			}
		}


	}
}
int main() {

	int N, K;

	cin >> N >> K;
	arr[N] = 0;

	
	if (N != K) {
		bfs(N, K);
		cout << arr[K];
	}
	
	else if (N == K) cout << 0;
	

}

minjoonist 4년 전 1

제 코드를 참고합니다.

#include <stdio.h>
#include <queue>
using namespace std;

int n, k;
int dirr[2]={1, -1};
bool visited[100001]={false};

struct st
{
    int x, cnt;
};
int bfs()
{
    queue<st> q;
    q.push({n, 0});
    visited[n]=true;
    while(!q.empty()){
        int curr=q.front().x, sec=q.front().cnt;
        q.pop();
        //printf("%d %d\n", curr, sec);
        for(int i=0; i<3; i++){
            int next;
            if(i==2) next=curr*2;
            else next=curr+dirr[i];
            if(next==k) return sec+1;
            if(next>=0 && next<=100000 && visited[next]==false){
                q.push({next, sec+1});
                visited[next]=true;
            }
        }
    }
}
int main()
{
    scanf("%d %d", &n, &k);
    if(n==k) puts("0");
    else printf("%d", bfs());
    return 0;
}

wjddydgns99 4년 전 1

위의 저의 답변을 너무 대충보신 것 같네요...;

위의 언급내용 + 몇가지 수정해서 정답코드 올려요.

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

int arr[100005] = { 0 };

void bfs(int N, int K) {

	queue<int> q;
	q.push(N);
	int tmp;

	while (!q.empty()) {

		tmp = q.front();
		q.pop();

		if (tmp == K) break;
		else {
			if (tmp * 2 <= 100000 && arr[tmp * 2] == -1) {
				arr[tmp * 2] = arr[tmp] + 1;
				q.push(tmp * 2);
			}
			if (tmp - 1 >= 0 && tmp - 1 <= 100000 && arr[tmp - 1] == -1) {
				arr[tmp - 1] = arr[tmp] + 1;
				q.push(tmp - 1);
			}
			if (tmp + 1 <= 100000 && arr[tmp + 1] == -1) {
				arr[tmp + 1] = arr[tmp] + 1;
				q.push(tmp + 1);
			}
		}


	}
	return;
}
int main() {

	int N, K;

	memset(arr, -1, sizeof(arr));
	cin >> N >> K;
	arr[N] = 0;


	if (N != K) {
		bfs(N, K);
		cout << arr[K];
	}

	else if (N == K) cout << 0;


}

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

문제

문제

출처

ICPC

런타임에러를 해결할 수 없습니다.. 도움부탁드립니다.

cheng1230 4년 전 0

wjddydgns99 4년 전 1

minjoonist 4년 전 1

cheng1230 4년 전 0

minjoonist 4년 전 1

wjddydgns99 4년 전 1

cheng1230 4년 전 0

minjoonist 4년 전 1

wjddydgns99 4년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말