[프로그래머스][C++] 네트워크

https://programmers.co.kr/learn/courses/30/lessons/43162

코딩테스트 연습 - 네트워크

 

[프로그래머스][C++] 네트워크

 

BFS, DFS, DFS with Stack...

#include <string>
#include <vector>
#include <queue>
#include <stack>

using namespace std;

void bfs(int n, int i, vector<vector<int>> computers, vector<int> &visit) {
	queue<int> q;
	q.push(i);
	visit[i] = 1;

	while (!q.empty()) {
		int f = q.front();
		q.pop();

		for (int j = 0; j < n; j++) {
			if (j == f) continue;
			if (computers[f][j] && !visit[j]) {
				q.push(j);
				visit[j] = 1;
			}
		}
	}
}

void dfs(int n, int i, vector<vector<int>> computers, vector<int> &visit) {
	visit[i] = 1;

	for (int j = 0; j < n; j++) {
		if (j == i) continue;
		if (computers[i][j] && !visit[j]) {
			dfs(n, j, computers, visit);
		}
	}
}

void dfsStack(int n, int i, vector<vector<int>> computers, vector<int>& visit) {
	stack<int> s;
	s.push(i);
	visit[i] = 1;

	while (!s.empty()) {
		int t = s.top();
		s.pop();

		for (int j = 0; j < n; j++) {
			if (j == t) continue;
			if (computers[t][j] && !visit[j]) {
				s.push(j);
				visit[j] = 1;
			}
		}
	}
}

int solution(int n, vector<vector<int>> computers) {
	int answer = 0;
	vector<int> visit(n, 0);

	for (int i = 0; i < n; i++) {
		if (visit[i]) continue;
        answer++;
		// bfs(n, i, computers, visit);
        // dfs(n, i, computers, visit);
        dfsStack(n, i, computers, visit);
	}

	return answer;
}