백준 1260번 DFS와 BFS

@ 그래프 탐색

  그래프를 탐색하는 방법인 깊이 우선 탐색(DFS : depth first search)과 너비 우선 탐색(BFS : breath first search)에 대해알아봅시다.

 

깊이 우선 탐색( DFS : depth first search )

- 깊이 우선 탐색의 탐색 순서는 시작 정점에서 시작하여 그 정점과 연결된 정점을 방문하고 다음에는 방문한 정점에서 다시 연결된 정점 순으로 방문한다. 진행하다가 더 이상 진행할 수 업스면 왔던 길을 거슬러 올라가면서 아직 방문하지 않은 정점을 방문하게 된다.

1. 스택을 이용해서 갈 수 있는 만큼 최대한 많이 가고
2. 갈 수없으면 이전 정점으로 돌아갑니다.
3. 스택에 넣을 때 방문했다고 체크해야 합니다.

 

너비 우선 탐색( BFS : breach first search )

- 너비 우선 탐색의 탐색 순서는 시작 정점을 먼저 방문하고 그 정점과 연결된 정점을 모두 방문한다. 다음으로 첫 번째로 연결된 정점으로 가서 그것과 연결된 정점들을 방문하고 다음으로 나머지 정점으로 가서 동일한 동작을 반복하게 된다.

1. 큐를 이용해서 지금 위치에서 갈 수 있는 모든 것을 큐에 넣는다
2. 큐에 넣을 때 방문했다고 체크해야 합니다.
   
   

DFS :  1 2 5 7 6 3 4      BFS :  1 2 3 4 5 6 7

 

DFS : 1 2 3 4 5 6 7 8 BFS : 1 2 5 3 7 4 8 6

 

 [ 백준 1260번 DFS와 BFS 문제 풀기 ]

www.acmicpc.net/problem/1260

1260번: DFS와 BFS

 

[ 백준 1260번 DFS와 BFS 문제 소스 코드 ]

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

int n,m,a,b,k;
int x[1010][1010]={0,};
bool check[1010];

void dfs(int k)
{
	printf("%d ",k);
	for(int i=1;i<=n;i++)
	{
		if(x[k][i]==1 && check[i]==false)
		{
			check[i]=true;
			dfs(i);
		}
	}
}

void bfs(int k)
{
	int i;
	queue<int> q;
	q.push(k);
	check[k]=true;
	while(!q.empty())
	{
		k=q.front();
		printf("%d ",k);
		q.pop();
		for(i=1;i<=n;i++)
		{
			if(x[k][i]==1 && check[i]==false)
			{
				check[i]=true;
				q.push(i);
			}
		}
	}
}

int main()
{
	int i,j;
	scanf("%d %d %d",&n,&m,&k);
	for(i=0;i<m;i++)
	{
		scanf("%d %d",&a,&b);
		x[a][b]=1;
		x[b][a]=1;
	}
	check[k]=true;
	dfs(k);
	printf("\n");
	for(i=1;i<=n;i++)
	{
		check[i]=false;
	}
	check[k]=true;
	bfs(k);
	return 0;
}