1260번 DFS와 BFS| baekjoon | C++

 

진짜 도저히 도저히 혼자 시도하다가 안 되겠어서

내가 짠 코드와 가장 유사한 방법으로 구현하신 한 블로거분의 코드를 따라해보았다.

 

[출처]

https://kimyunseok.tistory.com/26 

 

 

하... 난 언제쯤 혼자 코드를 작성해볼 수 있을까

여름 방학 때 백준 더 풀 걸 그랬다잉...~~~ 앞으로 더 노력해라 채숭아~

 

암튼!

 

---

 

 

문제

 

 

- DFS와 BFS를 이용해 탐색한 결과를 출력하는 문제였다.

 

- 내가 중요하게 생각한 부분은

방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하라는 조건이었다.

이 부분에서 많이 막혔다.

 

 

 

정답 코드

 

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

int vertex_cnt, edge_cnt, start_vertex_num;
vector<int> adj_list[1001]; // vector에서 () [] {} 로 초기화하면, 열은 고정이지만 행은 가변적이라고 함. =>????
bool visited_dfs[1001];
bool visited_bfs[1001];

void dfs(int cur_vectex_num) {
	cout << cur_vectex_num << " ";
	visited_dfs[cur_vectex_num] = true;
	for (int vertex : adj_list[cur_vectex_num]) {  // for (자료형 변수명 : 배열명) { 실행코드; }
		if (!visited_dfs[vertex]) {
			dfs(vertex);
		}
	}
}

void bfs(int start_vertex_num) {
	queue<int> q;
	q.push(start_vertex_num);
	visited_bfs[start_vertex_num] = true;
	while (!q.empty()) {
		int cur_vertex_num = q.front();
		q.pop();
		cout << cur_vertex_num << " ";
		for (int vertex : adj_list[cur_vertex_num]) {
			if (!visited_bfs[vertex]) {
				visited_bfs[vertex] = true;
				q.push(vertex);
			}
		}
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin >> vertex_cnt >> edge_cnt >> start_vertex_num;

	for (int i = 1; i <= edge_cnt; i++) {
		int source, dest;
		cin >> source >> dest;
		adj_list[source].push_back(dest);
		adj_list[dest].push_back(source);
	}

	for (int i = 1; i <= vertex_cnt; i++) {
		sort(adj_list[i].begin(), adj_list[i].end());
	}

	dfs(start_vertex_num);
	cout << '\n';
	bfs(start_vertex_num);

	return 0;

}

 

 

내 코드 & 보완할 점

 

[1차 코드] - 엉망임 

 

 

#include <iostream>
#include <queue>
#include <stack>
#include <list>
#include <vector>
using namespace std;

class Graph {
private:
	int data;
	int vertices; // 정점 갯수
	bool* visited; // 방문 여부
	vector<list<int>> adj; // 연결된 정점 정보

public:
	Graph(int _vertices) {
		vertices = _vertices; // 정점 갯수 초기화
		visited = new bool[_vertices];
		for (int i = 0; i < _vertices; i++) {
			visited[i] = false;
		}
		adj.resize(_vertices);
	}

	~Graph() {
		delete visited;
	}

	void setUndirectEdges(int _a, int _b) {
		adj[_a].push_back(_b);
		adj[_b].push_back(_a);
	}
	void setDirectEdges(int _a, int _b) {
		adj[_a].push_back(_b); // 방향성이 있으므로 하나만 삽입
	}

	void BFS(int _start) {
		queue<int> Q;
		Q.push(_start);
		visited[_start] = true;
		while (!Q.empty()) {
			_start = Q.front();
			Q.pop();
			cout << _start + 1 << ' ';
			list<int>::iterator iter; //이터레이터
			for (iter = adj[_start].begin(); iter != adj[_start].end(); ++iter) {
				if (!visited[*iter]) {
					visited[*iter] = true;
					Q.push(*iter);
				}
			}
		}
	}

	void DFS(int _start) {
		stack<int> S;
		S.push(_start);
		visited[_start] = true;
		while (!S.empty()) {
			_start = S.top();
			S.pop();
			cout << _start + 1 << ' ';
			list<int>::iterator iter; //이터레이터
			for (iter = adj[_start].begin(); iter != adj[_start].end(); ++iter) {
				if (!visited[*iter]) {
					visited[*iter] = true;
					S.push(*iter);
				}
			}
		}
	}

	void initializing_visited() {
		for (int i = 0; i < vertices; i++) {
			visited[i] = false;
		}
	}

	void descending_adj() {
		for (int i = 0; i < vertices; i++) {
			sort(adj[i].begin(), adj[i].end());
		} adj -> vecter<list<int>>
	}
};

int main() {

	int N, M, v;
	cin >> N >> M >> v;

	Graph MyGraph(N);

	int a, b;
	for (int i = 0; i < M; i++) {
		cin >> a >> b;
		MyGraph.setUndirectEdges(a-1, b-1);
	}

	MyGraph.descending_adj();
	MyGraph.DFS(v-1);
	MyGraph.initializing_visited();
	cout << '\n';
	MyGraph.BFS(v-1);

	return 0;
}

 

문법도 오락가락하고 error도 개많이 남.

 

그래서 일단 먼저 vector에 대해 정리하고

코드를 다시 짜보기로 했음!

 

[2차 코드] - 성공!!!