(백준 1260번 DFS와 BFS C++) 라이님 블로그 대회 알고리즘 따라잡기 9) BFS 4

백준 1260번

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

1260번: DFS와 BFS

 

DFS와 BFS를 알고 있으면 어렵지 않게 구현이 가능한 문제다. 

 

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

class Graph {
public:
	int N, M; 
	vector<vector<int>> adj;
	vector<bool> visited;
	Graph(int N, int M) : N(N), M(M), adj(N+1), visited(N+1){}

	void addEdge(int u, int v) {
		adj[u].push_back(v);
		adj[v].push_back(u);
	}

	void unique_sort(){
		// ★ N과 M 구분 ★ i의 범위
		for (int i = 1; i <= N; i++) {
			sort(adj[i].begin(), adj[i].end());
			adj[i].erase(unique(adj[i].begin(), adj[i].end()), adj[i].end());
		}
	}

	void dfs(int V) {
		fill(visited.begin(), visited.end(), 0);
		int curr = V; cout << V << " ";
		dfs_sub(V);	
	}

	void bfs(int curr) {
		fill(visited.begin(), visited.end(), 0);
		queue<int> Q;
		cout << curr << " ";
		Q.push(curr); visited[curr] = true;

		while (!Q.empty()) {
			curr = Q.front();
			Q.pop();
			for (int next : adj[curr]) {
				if (!visited[next]) {
					cout << next << " ";
					Q.push(next);
					visited[next] = true;
				}
			}
		}
		
	}
private:
	void dfs_sub(int curr) {
		visited[curr] = true;
		for (int next : adj[curr]) {
			if (!visited[next]) {
				cout << next << " ";
				visited[next] = true;
				dfs_sub(next);
			}
		}
	}
};

int main() {
	int N, M, V; cin >> N >> M >> V;

	Graph g(N, M);

	for (int i = 0; i < M; i++) {
		int u, v; cin >> u >> v;
		g.addEdge(u, v);
	}
	g.unique_sort();

	g.dfs(V); cout << endl;
	g.bfs(V);
}

 

N과 M 구분 / i 의 범위 때문에 틀렸었다!!

 

자주 헷갈리는 부분인데, 테스트케이스에서는 안 걸리는 일이 많기 때문에 항상 조심하면서 사용하는 습관을 가져야겠다

 

ㅋㅋㅋㅋㅋ웃기다. algorithm을 include 하지 않아서 생긴 일,,!