1260. DFS와 BFS

1260 DFS와 BFS

DFS와 BFS의 기초 문제

그래프를 DFS, BFS로 출력하기

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

---

문제 풀이

• 그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램 만들기
• 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고,
  더 이상 방문할 수 있는 점이 없는 경우 종료

입력

• 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), int N 간선의 개수 M(1 ≤ M ≤ 10,000), int M 탐색을 시작할 정점의 번호 V가 주어진다. int V

• 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사이에 여러 개의 간선이 있을 수 있다. 입력으로 주어지는 간선은 양방향이다

  • 간선의 정보를 저장할 연결리스트 2중 벡터 사용 vector< vector<int> >

출력

첫째 줄에 DFS를 수행한 결과를, 그 다음 줄에는 BFS를 수행한 결과를 출력한다. V부터 방문된 점을 순서대로 출력하면 된다.

코드

의사코드

1. 2차원 벡터를 이용해 연결리스트를 입력받음
   • ** 주의! 간선은 양방향이므로 연결리스트에 추가할때 map[start].push(end) 와 반대 방향인 map[end].push(start)도 추가해줘야함
2. 각 노드의 연결리스트를 오름차순으로 정렬해준다
   • 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문해야하기 때문
3. DFS로 출력
   • 노드 V를 방문처리한다
   • 노드 부터 시작해서 DFS시작
     • 현재 노드 출력
     • 현재 노드와 연결된 노트 검색
     • 존재한다면 방문한 적이 있는지 체크
       • 방문했던 노드라면 패스
       • 방문하지 않았다면 방문 처리후 DFS(next) 호출

4. 방문처리했던 visited 배열을 0으로 초기화한다

5. BFS로 출력
   • 큐에 V노드를 넣고 방문처리
   • 큐가 빌때까지 다음을 반복한다
     • 큐의 맨 앞의 노드를 가져와 now에 저장
     • now를 출력
     • now와 연결된 노드가 있는지 확인후 방문 체크
       • 방문했던 노드라면 패스
       • 방문하지 않았다면 큐의 맨 뒤에 넣는다

소스코드

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

int N, M, V;
vector< vector<int> > map;
int visited[1001] = { 0 };

void DFS(int now) {
	cout << now << " ";

	// 현재 노드와 연결된 노드 찾기
	for (int i = 0; i < map[now].size(); i++) {
		int next = map[now][i];
		if (visited[next] == 1) continue;
		visited[next] = 1;
		DFS(next);
	}

}

void BFS(int start) {
	queue<int> qu;

	visited[V] = 1;
	qu.push(start);

	while (!qu.empty()) {
		int now = qu.front();
		qu.pop();

		cout << now << " ";

		for (int i = 0; i < map[now].size(); i++) {
			int next = map[now][i];
			if (visited[next] == 1) continue;
			visited[next] = 1;
			qu.push(next);
		}

	}


}

int main() {
	freopen_s(new FILE*, "input.txt", "r", stdin);

	cin >> N >> M >> V;

	map.resize(N + 1);

	while (M--) {
		int start, end;
		cin >> start >> end;
		map[start].push_back(end);
		map[end].push_back(start);
	}

	for (int i = 0; i < N + 1; i++) {
		sort(map[i].begin(), map[i].end());
	}
	
	visited[V] = 1;
	DFS(V);
	cout << "\n";

	fill(visited, visited + 1001, 0);

	BFS(V);

	return 0;
}

---