글 읽기 - dfs맞았는데 bfs로 틀리네요 어떤경우에서 안되는걸까요 ?

scared22 6년 전 0

dfs코드를 한번 bfs로 바꿔봤는데 자꾸 틀렸다고 뜨네요 어떤경우에서 안되는지 알고 싶습니다.

#include <iostream>
#include <queue>
using namespace std;
int n, p1,p2,m,x,y,map[1005][1005],check[1005];

int main()
{
	queue<int>bfs;
	cin>>n;
	cin>>p1>>p2;
	cin>>m;
	for(int i=0;i<m;i++)
	{c
		cin>>x>>y;
		map[x][y]=1;
		map[y][x]=1;
	}
	bfs.push(p1);
	check[p1]=1;
	int cnt=0;
	while(!bfs.empty())
	{
		int size = bfs.size();
		while(size--)
		{
			int pos = bfs.front();
			bfs.pop();
			if(pos == p2)
			{
				cout<<cnt<<"\n";
				return 0;
			}
			for(int i=1;i<=n;i++)
			{
				if(map[pos][i]==1 && check[i]==0)
				{
					check[i]=1;
					bfs.push(i);
				}
			}
		}
		cnt++;
	}
	if(cnt==0)cout<<-1<<"\n";
}

zlzmsrhak 6년 전 0

코드에서는 친척 관계가 없어 촌수 계산이 되지 않는 경우에 아무것도 출력을 안할 수 있습니다.

반례입니다.

1 3

1 2

sgchoi5 6년 전 0

if(cnt==0) cout<<-1<<"\n"; 에서 if(cnt==0) 은 안 해도 되는 코드 입니다.

loop 를 돌면서 단계별로 step 을 증가시키면서 찾게 되면 그 단계를 출력하면 되고,

못찾게 되면 그냥 -1 입니다. cnt 는 올라갈 수 있거든요.

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

문제

문제

출처

ICPC

dfs맞았는데 bfs로 틀리네요 어떤경우에서 안되는걸까요 ?

scared22 6년 전 0

zlzmsrhak 6년 전 0

sgchoi5 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말