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

분류 : dfs/bfs

 

요구사항

연결된 네트워크 사이클 구하기

 

풀이

dfs로 풀이하면 직관적으로 풀 수 있으나, bfs로 풀어보고 싶어 bfs로 풀어보았다

1. i->j로 연결되있고, 방문한 적이 없으면 bfs를 시작한다.

2. i에 연결되어 있는 노드를 큐에 넣고, visit[node]=1로 설정한다.

3. 큐가 빌때까지 1~2반복한다

 

#include <string>
#include <vector>
#include <queue>
#include <string.h>
#include <iostream>

using namespace std;
struct go {
	int x;
	int y;
};
int solution(int n, vector<vector<int>> computers) {
	int answer = 0;
	int visit[220] = { 0, };
	int qvisit[220][220] = { 0, };
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (computers[i][j] == 1) {
				if (visit[j] == 0) {
					visit[i] = 1;
					queue<int> q;
					answer++;
					q.push(i);
					while (!q.empty()) {
						
						int now = q.front();
						q.pop();
						for (int k = 0; k < computers[now].size(); k++) {
							
							int next = computers[now][k];
							if (computers[now][k] == 1) {
								if (visit[k] == 0) {
									cout << k << endl;
									visit[k] = 1;
									q.push(k);
								}
							}
						}

					}
					

				}
			}
		}
	}
	return answer;
}