[백준 1260번 C/C++] DFS와 BFS

 

목차

 

 

---

 

 

 

[백준 1260번 C/C++] DFS와 BFS

 

https://www.acmicpc.net/problem/1260

1260번: DFS와 BFS

---

 

해결전략

 

vector<int> graph[ ]

• 정점

 

int Dv[ ]

• DFS 정점 방문 체크

 

int Bv[ ]

• BFS 정점 방문 체크

 

int dis[ i ]

• 정점 i 의 방문 순서.

 

int cnt = 1

• 방문 카운팅
• "시작 정점의 방문 순서는 1이다."라고 문제에서 명시되어 있다. 따라서 int cnt의 시작값을 1로 설정.

 

queue<int> Q

• 방문한 정점을 담은 다음 후에 다시 꺼내는 방식으로 BFS를 구현한다.

---

 

 

 

코드

 

#include<stdio.h>
#include<vector>
#include<queue>
#include<algorithm>
using namespace std;

vector<int> graph[100001];
int Dv[100001], Bv[100001];
queue<int> Q;

void DFS(int x)
{
	if (Dv[x]==1) return;
	else
	{
		Dv[x]=1;
		printf("%d ", x);
		
		for(int i=0; i<graph[x].size(); i++)
		{
			if (Dv[graph[x][i]]==0)
				DFS(graph[x][i]);
		}
	}
}

void BFS(int x)
{
	Q.push(x);
	Bv[x]=1;
	
	while(!Q.empty())
	{
		x=Q.front();
		Q.pop();
		printf("%d ", x);
		
		for(int i=0; i<graph[x].size(); i++)
		{
			if(Bv[graph[x][i]]==0)
			{
				Bv[graph[x][i]]=1;
				Q.push(graph[x][i]);
			}
		}
	}
}

int main() {
	freopen("input.txt", "rt", stdin);
	int n, m, v;
	scanf("%d %d %d", &n, &m, &v);
	
	for (int i = 1; i <= m; i++) {
		int a, b;
		scanf("%d %d", &a, &b);
		graph[a].push_back(b);
		graph[b].push_back(a);
	}
	for (int i = 1; i <= n; i++) {
		sort(graph[i].begin(), graph[i].end());
	}
	
	DFS(v);
	printf("\n");
	BFS(v);
		
	return 0;
}

 

 

 

 

유사문제

 

만약 각각의 간선길이(=가중치)를 구하고 싶다면?

#include<stdio.h>
#include<vector>
#include<queue>
#include<algorithm>
using namespace std;

vector<int> graph[100001];
int Dv[100001], Bv[100001], DFSdis[100001], BFSdis[100001], DFScnt=0, BFScnt=1;
queue<int> Q;

void DFS(int x)
{
	if (Dv[x]==1) return;
	else
	{
		Dv[x]=1;
		DFScnt++;
		DFSdis[x]=DFScnt;
		
		for(int i=0; i<graph[x].size(); i++)
		{
			if (Dv[graph[x][i]]==0)
				DFS(graph[x][i]);
		}
	}
}

void BFS(int x)
{
	Q.push(x);
	Bv[x]=1;
	
	while(!Q.empty())
	{
		x=Q.front();
		Q.pop();
		BFSdis[x]=BFScnt++;
		
		for(int i=0; i<graph[x].size(); i++)
		{
			if(Bv[graph[x][i]]==0)
			{
				Bv[graph[x][i]]=1;
				Q.push(graph[x][i]);
			}
		}
	}
}

int main() {
	freopen("input.txt", "rt", stdin);
	int n, m, v;
	scanf("%d %d %d", &n, &m, &v);
	
	for (int i = 1; i <= m; i++) {
		int a, b;
		scanf("%d %d", &a, &b);
		graph[a].push_back(b);
		graph[b].push_back(a);
	}
	for (int i = 1; i <= n; i++) {
		sort(graph[i].begin(), graph[i].end());
	}
	
	DFS(v);
	BFS(v);
	
	for(int i=1; i<=n; i++)
	{
		printf("%d ", DFSdis[i]);
	}	
	printf("\n");
	
	for(int i=1; i<=n; i++)
	{
		printf("%d ", BFSdis[i]);
	}
		
	return 0;
}

 

 

vector<int> graph[ ]

• 정점

 

int Dv[ ], Bv[ ]

• DFS 정점 방문 체크,
• BFS 정점 방문 체크

 

int DFSdis[ i ], BFSdis[ i ]

• 정점 i 의 방문 순서.

 

DFScnt = 0

• DFS 방문 카운팅

 

int BFScnt = 1

• BFS 방문 카운팅
• "시작 정점의 방문 순서는 1이다."라고 문제에서 명시되어 있다. 따라서 int cnt의 시작값을 1로 설정.

 

queue<int> Q

• 방문한 정점을 담은 다음 후에 다시 꺼내는 방식으로 BFS를 구현한다.

---