글 읽기 - BFS 시 visit 여부 체크 시점 문의드립니다.

shfshfdl 4년 전 1

BFS 시 visit 여부 체크 시점 문의드립니다.

BFS로 풀때 queue에 넣기 전에 visit을 체크해줘야지 중복으로 체크가 되지 않아

타임아웃이 발생하지 않는다고 알고 있는데

이 문제의 경우는 visit 시점이 +1 , -1, *2 를 처리한 값에 visit여부를 체크해서

성공을 받긴 햇는데 이런 경우 중복 체크가 될 것 같은데

제가 잘 못이해한 부분이 있을까요?

감사합니다.

#include <iostream>
#include <queue>
#define MXN 100000
#define INF 987654321
using namespace std;
int N, K;
int visit[MXN + 1] = { 0, };
queue<int> q;
int cnt = 0, time = 0;

void bfs(int here) {
	visit[here] = true;
	q.push(here);

	while (!q.empty()) {
		int q_size = q.size();
		for (int i = 0; i < q_size; i++) {
			int there = q.front(); q.pop();
			if (there == K) cnt++;
			visit[there] = true;

			if (there + 1 <= MXN && !visit[there + 1]) q.push(there + 1);
			if (there - 1 >= 0 && !visit[there - 1]) q.push(there - 1);
			if (there * 2 <= MXN && !visit[there * 2]) q.push(there * 2);
		}
		if (cnt != 0) return;
		time++;
	}
}

int main() {
	cin >> N >> K;
	bfs(N);
	if (N == K) cout << 0 << endl << 1 << endl;
	else cout << time << endl << cnt << endl;

	return 0;
}

lim551 4년 전 3

q를 뽑고 나서 visit을 체크하면 당연히 중복이 생깁니다. 그러나 이 문제의 경우 그 중복이 그렇게 크지 않습니다. +1로 인해 방문된 정점과 *2로 인해 방문된 정점이 중복되어 큐에 저장되긴 하지만, 2배씩 뛰는 경우 자체가 얼마 되지 않기 때문에 큰 중복이 발생하지는 않는 것 같습니다.

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

문제

문제

출처

ICPC

BFS 시 visit 여부 체크 시점 문의드립니다.

shfshfdl 4년 전 1

lim551 4년 전 3

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말