글 읽기 - 1697번 숨바꼭질 BFS 질문입니다! 헬프미~

xotmd17 5년 전 0

질문검색내용을 보면 갔던 곳을 다시 가지 않게만 하면 BFS를 사용해서 가능하다고 했는데

왜 런타임에러가 나는 것 인지 모르겠습니다. 1 12004 까지만 가능합니다.

오류가 나는 이유가 무엇인지 알려주세요 ㅠㅜ

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

int N, K;
int X[100001];
int dx[3] = {-1, 1, 0}; //움직이는 경우의 수 3가지
queue<int> que;

int BFS(int n)
{
	que.push(n);
	X[n] = 1;

	while(!que.empty())
	{
		int x = que.front();
		que.pop();
		if(x == K)
			return X[K];
		dx[2] = x;
		for(int i=0; i<3; i++)
		{
			int qx = x + dx[i]; // -1, 1, 해당값 을 더해준다.
			if(X[qx] == 0 && qx >= 0 && qx <= 100000) // 0은 간적이 없던 곳이다.
			{
				X[qx]=X[x]+1; //간적이 없던 곳이면 +1씩 쌓아간다.
				que.push(qx);
			}
		}
	}
}

int main(void)
{
	cin >> N >> K;

	if(N > K) //N이 K보다 크면 -1 이동으로 밖에 갈 수 없으므로 그냥 N-K를 한다.
	{
		cout << N-K << endl;
		return 0;
	}

	BFS(N);
	cout << X[K]-1 << endl;
}

djm03178 5년 전 1

qx가 0보다 작거나 100000보다 커질 수 있으니 범위 검사를 해야 합니다.

xotmd17 5년 전 0

if(X[qx] == 0 && qx >= 0 && qx <= 100000)

한번도 간적 없고, 0과 100000 사이일때만 가는 조건입니다.

이 부분이 검사를 하는 것으로는 안되는 건가요?

djm03178 5년 전 1

앗 제대로 못 보고 답변했네요. 이 경우 X[qx]에 접근하는 작업을 먼저 하는데 그 자체가 문제가 됩니다. 범위 검사를 먼저 하고, 그 뒤에 배열의 그 칸을 봐야 됩니다.

xotmd17 5년 전 0

감사합니다.

if(X[qx] == 0 && qx >= 0 && qx <= 100000)를

if(qx >= 0 && qx <= 100000 && X[qx] == 0)로 바꾸니깐 성공은 했습니다.

그런데 어째서 이 차이하나로 안되는 건지 알려주실 수 있나요?

&&로 묶었는데 이렇게 되는걸 까요?

앞의 범위조건을 벗어나면 뒤 조건을 확인하지 않는 것 때문인가요?

조건 몇 번 때문에 런타임이 날 수도 있는건가요?

C++에는 short-circuit evaluation이라는 것이 있어서, 논리 AND나 OR 연산에 대해 좌항을 먼저 평가한 뒤, 그로 인해 전체 식의 참/거짓이 결정될 경우 우항은 실행하지 않습니다. AND의 경우 좌항이 false이면 우항의 결과에 관계없이 전체 false가 확정되므로, 우항의 내용은 아예 실행하지 않게 됩니다. 반대로 OR의 경우 좌항이 true이면 우항의 결과에 관계없이 전체 true가 확정되므로 우항은 실행되지 않습니다.

만일 qx가 0보다 작거나 100000보다 크다면 X[qx] == 0의 결과에 관계없이 전체 식이 false인 것이 확정이므로 X[qx] == 0은 아예 실행하지 않게 됩니다.

xotmd17 5년 전 0

그냥 조건이 3개뿐이라 별 생각없었는데 좌항으로 인해 X[qx] == 0이 실행되냐 안되냐의 차이 하나로 문제가 풀리고 안풀릴 수 있다는 걸 알게되었습니다.

감사합니다.

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

문제

문제

출처

ICPC

1697번 숨바꼭질 BFS 질문입니다! 헬프미~

xotmd17 5년 전 0

djm03178 5년 전 1

xotmd17 5년 전 0

djm03178 5년 전 1

xotmd17 5년 전 0

djm03178 5년 전 2

xotmd17 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말