[백준 1260] DFS와 BFS

문제 링크

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

1260번: DFS와 BFS

 

 

 

문제 풀이

#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <queue>
using namespace std;

//전역 변수 선언부
vector<int> e[1001];
bool visited[1001];

//DFS
void dfs(int v) {
	visited[v] = true;
	cout << v << " ";
	for (int i = 0; i < e[v].size(); i++) {
		int next = e[v][i];
		if (!visited[next])
			dfs(next);
	}
}

//BFS
void bfs(int v) {
	queue<int> q;
	q.push(v);
	visited[v] = true;
	while (!q.empty()) {
		int cur = q.front();
		q.pop();
		cout << cur << " ";
		for (int i = 0; i < e[cur].size(); i++) {
			int next = e[cur][i];
			if (!visited[next]) {
				visited[next] = true;
				q.push(next);
			}
		}
	}
}

int main(void) {
	//입출력 속도 차이 해결
	ios::sync_with_stdio(0);
	cin.tie(0);

	int N, M, V, from, to;

	//정점, 간선, 시작할 정점의 번호
	cin >> N >> M >> V;

	for (int i = 0; i < M; i++) {
		cin >> from >> to;
		e[from].push_back(to);
		e[to].push_back(from);
	}

	for (int i = 1; i <= N; i++)
		sort(e[i].begin(), e[i].end());
	dfs(V);
	cout << '\n';
	memset(visited, false, sizeof(visited));
	bfs(V);

	return 0;
}

 

문제 풀이

• 1~6번 라인: 라이브러리 선언 
• 8번 라인: 인접리스트를 저장할 vector를 정점의 최대 개수가 1000이므로 e[1000]에 접근을 위해 1001로 크기 지정
• 9번 라인: 정점의 방문을 체크할 배열 visited도 마찬가지 이유로 1001의 크기로 선언
• 40 ~ 41번 라인: 입출력 속도차이를 해결하기 위한 선언으로 40번 라인은 C와 C++표준 stream 동기화를 끊기 위한 것이고, cin.tie(0); cout.tie(0);는 cin을 cout으로부터 untie한다. stream을 tie하면 다른 stream에서 입출력이 오기 전에 stream을 flush시킨다. 그리고 scanf와 printf와 섞어서 사용하지 않도록 한다.
• 45~49번 라인 : 입력으로 주어지는 간선은 양방향이므로 인접 리스트에 양방향으로 저장합니다.
• 51~52번 라인 : 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문해야 하기 때문에 오름차순으로 정렬합니다.
• 53번 라인 : 탐색을 시작할 정점 V를 넘겨주면서 DFS 함수를 호출합니다.
• 11~19번 라인 : 재귀함수를 이용한 DFS입니다.
• 12번 라인 : 정점을 방문할 때 마다 visited[v]를 true로 바꿔주면서 방문한 것을 표시하고,
• 13번 라인 : 해당 정점을 출력합니다.
• 14번 라인 : 다음에 방문할 정점을 찾기 위해 현재 방문한 정점과 이어져 있는 정점의 개수만큼 for문을 돌면서,
• 15번 라인 : next변수에 현재 방문한 정점과 이어져 있는 정점을 저장하고,
• 16번 라인 : next정점을 방문한 적이 없으면(visited[next] == false)
• 17번 라인 : next정점을 넘겨주면서 DFS 함수를 호출합니다.
• 55번 라인 : visited 배열을 다시 false로 초기화하기 위해 memset함수를 이용합니다.
• 56번 라인 : 탐색을 시작할 정점 V를 넘겨주면서 BFS 함수를 호출합니다.
• 21~37번 라인 : queue를 이용한 BFS입니다.
• 23번 라인 : 처음 방문한 정점 v를 q에 push합니다.
• 25번 라인 : 처음 방문한 정점을 표시하기 위해 visited[v]를 true로 바꿔줍니다.
• 25번 라인 : q가 비어있지 않는 동안
• 26번 라인 : cur변수에 현재 방문한 정점을 q.front()를 이용하여 저장
• 27번 라인 : q.pop()을 이용하여 q에서 빼주고,
• 28번 라인 : 현재 방문한 정점을 출력.
• 29번 라인 : 다음에 방문할 정점을 찾기 위해 현재 방문한 정점과 이어져 있는 정점의 개수만큼 for문 루프.
• 30번 라인 : next변수에 현재 방문한 정점과 이어져 있는 정점을 저장
• 31번 라인 : next정점을 방문한 적이 없으면(visited[next] == false)
• 32번 라인 : next정점을 방문하였다고 표시한 후(visited[next] = true)
• 33번 라인 : q에 next정점을 push.