글 읽기 - 한 50퍼쯤에서 나가리되는데 이해가 안됩니다..

ploffer11 5년 전 0

이거 그냥 정점 1에서 bfs한번 돌려서 각 노드까지 도달하는데 걸리는 거리 배열에 저장해놓고

들어오는 입력이 "비내림차순" 이면 올바른 bfs, 아니면 틀린 bfs 아닌가요??

왜 틀리는 건지 모르겠습니다.

#include <iostream>
#include <vector>
#include <queue>
#include <tuple>
using namespace std;
typedef pair<int, int> pii;

int level[100005], inp[100005];

vector<int> vt[100005];

void bfs()
{
	queue<pii> q;
	level[1] = 1;
	q.push(pii(1, 1));

	while ( !q.empty() )
	{
		auto[lev, node] = q.front();
		q.pop();

		for ( auto e : vt[node] )
		{
			if ( !level[e] )
			{
				level[e] = lev + 1;
				q.push(pii(lev + 1, e));
			}
		}
	}
}

int main()
{
	int n; cin >> n;
	for ( int i = 0; i < n - 1; i++ )
	{
		int a, b;
		cin >> a >> b;
		vt[a].push_back(b);
		vt[b].push_back(a);
	}

	bfs();

	for ( int i = 0; i < n; i++ )
	{
		int x; cin >> x;
		inp[i] = level[x];
	}

	for ( int i = 1; i < n; i++ )
	{
		if ( inp[i - 1] > inp[i] )
		{
			cout << "0";
			return 0;
		}
	}

	cout << "1";
}

startlink 5년 전 1

네 방법이 틀렸습니다.

ploffer11 5년 전 0

아...........

chemistrae03 님 감사합니다.

올바른 bfs라면 큐에 일관되게 주어져야 겠군요..

디버그 할 방법을 생각해보도록 하겠습니다.

jh05013 5년 전 0

문제 설명은 매우 충분합니다. "2-3단계"가 아니라 "2-2단계"일 뿐이죠.

startlink 5년 전 0

방문하지 않은 정점은 순서에 상관 없이 방문해도 되는 것이 맞습니다.

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

문제

문제

출처

ICPC

한 50퍼쯤에서 나가리되는데 이해가 안됩니다..

ploffer11 5년 전 0

startlink 5년 전 1

ploffer11 5년 전 0

jh05013 5년 전 0

startlink 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말