개요

백준 1260번: DFS와 BFS

• 입력
  첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사이에 여러 개의 간선이 있을 수 있다. 입력으로 주어지는 간선은 양방향이다.

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

접근 방식

1. 그래프 객체를 생성 후 dfs와 bfs 함수를 구현해줬다.

2. 문제의 조건으로는 노드의 인접노드들을 정렬해줘야한다.

   각 정점끼리 여러개 간선 가질수 있다는 조건은
   방문 여부 저장하는 배열 사용으로 해결된다.

코드

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

using namespace std;

int nodes = 0, edges = 0, initNode = 0;

/// <summary>
/// bfs, dfs 함수 정의한 그래프 객체
/// </summary>
class Graph {
public:
	//각 노드의 인접 노드 담은 2차원 벡터
	vector<vector<int>> adj;
	//각 노드의 방문 여부 저장한 벡터
	vector<int> visited;
	//bfs에서 사용될 큐
	queue<int> q;

	//생성자
	Graph() {
		//2차원 벡터 1001만큼 메모리 미리 할당해주기
		adj.resize(1000 + 1);
		//방문 벡터 1001만큼 메모리 미리 할당해주기
		visited.resize(1000 + 1);
	}

	//간선 이어주는 함수(양방향 그래프)
	void addEdge(int u, int v) {
		adj[u].push_back(v);
		adj[v].push_back(u);
	}
	
	//각 노드의 인접노드 sort해야함
	void sortVertex() {
		for (int i = 1; i <= nodes; i++) {
			sort(adj[i].begin(), adj[i].end());
		}
	}
	//dfs함수
	void dfs(int Node) {
		if (visited[Node]) return;
		visited[Node] = true;
		cout << Node<<" ";
		for (int elem : adj[Node]) {
			if (!visited[elem]) {
				dfs(elem);
			}
		}
	}
	//bfs함수
	void bfs(int Node) {
		q.push(Node);
		visited[Node] = true;
		while (!q.empty()) {
			int cur = q.front();
			cout << cur << ' ';
			q.pop();
			for (int elem : adj[cur]) {
				if (!visited[elem]) {
					visited[elem] = true;
					q.push(elem);
				}
			}
		}
	}
};
//전역 변수로 선언
Graph* g;

void input() {
	int node1=0,node2=0;
	cin >> nodes >> edges >> initNode;
	g = new Graph();
	for (int i = 0; i < edges; i++) {
		cin >> node1 >> node2;
		g->addEdge(node1,node2);
	}
	g->sortVertex();

}
void solution() {
	g->dfs(initNode);
	cout << '\n';
	//visited 1001까지 false해줘서 통과
	fill(&g->visited[1], &g->visited[1001], false);
	g->bfs(initNode);
}

int main() {
	input();
	solution();
}

문풀후생

정점은 1부터 1000까지 들어올수 있으므로
방문 여부 저장한 배열 초기화 시킬때

//이렇게 1001까지 초기화시켜야함
	fill(&g->visited[1], &g->visited[1001], false);

1부터 1001까지 초기화 시켜야되는데 1부터 1000까지만 초기화 시켜서
틀렸습니다가 계속 떴다..