글 읽기 - dfs bfs 어느부분이 틀렸나요....

chkwon91 10년 전 0

예제는 만족하는데,,, 제출하면 틀렸다고 나오네요.

문제푸는건 밑에 주석으로 두었습니다..

어떤 입력값에서 제가 틀린지 부탁드려요 ㅠㅠ

#include<iostream>
#include<vector>
#include<stack>
#include<math.h>
#include<set>
#include<algorithm>

#include<fstream>

using namespace std;

int main()
{
	int N,M,start;
	int i, j, k;
	stack<int> s;
	vector<int> dfs,bfs,v1,v2;
	set<int> s1, s2;
	set<int>::iterator piv;
	
	bool vertex[1000];
	bool map[1001][1001];	//map은 간선을 나타내며 간선이 존재하면 true, 존재하지 않으면 false이다

	ifstream ifp("Input.txt");

	ifp>>N>>M>>start;
	//cin>>N>>M>>start;

	for(i=1;i<=N;i++){
		vertex[i]=false;
		for(j=1;j<=N;j++)
		{map[i][j]=false;}
	}

	for(i=0; i<M; i++)
	{
		ifp>>j>>k;
		//cin>>j>>k;
		map[j][k]=true;	map[k][j]=true;
	}

	/*dfs*/

	dfs.push_back(start);	s.push(start);	vertex[start]=true;
	
	/*stack을 이용해서 구현하였다*/
	while(1)
	{
		if(s.empty())	break;

		i=1;
		while(i<=N)//for(i=1;i<=N;i++)
		{
			if(map[s.top()][i]==true&&vertex[i]==false)
			{
				dfs.push_back(i);	s.push(i);	vertex[i]=true;
				break;
			}
			i++;
		}
		if(i>N)	{s.pop();}	//i가 N보다 큰 경우는 방문할 정점이 없다는 뜻이므로
	}

	/*bfs*/
	
	for(i=1;i<=N;i++){vertex[i]=false;}

	s1.insert(start);	vertex[start]=true;

	/*두개의 집합을 이용해서 구현하였다 s1과 s2는 다른 breadth를 나타낸다*/
	while(1)
	{
		if(s1.empty()&&s2.empty())	{break;}
		
		for(piv=s1.begin();piv!=s1.end();piv++)
		{
			bfs.push_back(*piv); //결과값을 입력한다
			for(j=1; j<=N; j++)
			{
				if(map[*piv][j]==true&&vertex[j]==false)/*안가본곳을 방문한곳으로 만든다*/
				{
					s2.insert(j);	vertex[j]=true;
				}
			}
		}
		s1.clear();

		for(piv=s2.begin();piv!=s2.end();piv++)
		{
			bfs.push_back(*piv);
			for(j=1; j<=N; j++)
			{
				if(map[*piv][j]==true&&vertex[j]==false)/*안가본곳을 방문한곳으로 만든다*/
				{
					s1.insert(j);	vertex[j]=true;
				}
			}
		}
		s2.clear();
		
	}
	cout<<dfs[0];for(i=1;i<dfs.size();i++)	{cout<<" "<<dfs[i];}cout<<endl;
	cout<<bfs[0];for(i=1;i<bfs.size();i++)	{cout<<" "<<bfs[i];}cout<<endl;

	return 0;
}

Nada 10년 전 3

7 6 1

1 4

1 3

1 2

4 6

4 5

2 7

1 2 3 7 4 5 6

1 2 3 4 7 5 6

bfs 탐색에서 깊이가 같을 때 부모 정점 번호가 작을 수록 우선이면서

부모 정점 번호가 같을 경우 정점 번호가 작은 것을 우선으로 계산하면 됩니다.

(현재 노드에서 방문할 수 있는 곳이 여러 곳 있을 때 작은 것 부터)

저도 헷갈리네요.

chkwon91 10년 전 1

@Nada 부모의 정점 번호가 작을수록 우선이군요... 몰랐습니다 ㅠ

혹시 Nada님의 예제 답중 첫번째가 dfs의 출력결과인가요?

dfs라면 1 2 7 3 4 5 6 이 아닌가요? 제가 틀린건가... 답이 계속 틀렸다나오네요

wwiiiii 10년 전 1

1 2 7 3 4 5 6이 dfs결과 맞습니다.

Nada 10년 전 1

앗 잘못 쳤네요 dfs 답이 1 2 7 3 4 5 6 입니다

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

문제

문제

출처

ICPC

dfs bfs 어느부분이 틀렸나요....

chkwon91 10년 전 0

Nada 10년 전 3

chkwon91 10년 전 1

wwiiiii 10년 전 1

Nada 10년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말