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

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

프로그래머스

풀이

같은 네트워크인지 확인하기 위해 한 바퀴를 돌아봐야하니 DFS/BFS로 접근하고자 했다.

BFS로 코드를 짰으며 ,

 

1) 0~n-1 컴퓨터까지 반복문으로 같은 네트워크에 속해있는지 확인하기 위해 BFS실행

2) 각자 컴퓨터 번호에 맞게 배열을 순회하면서 자신과 번호와 다르며, 방문하지 않았고, 연결된(1) 컴퓨터를 방문처리

3) BFS가 끝날때마다 네트워크 1가 추가되며, 모든 컴퓨터가 방문처리되면 반복문종료

---

#include <string>
#include <vector>
#include <queue>
using namespace std;
int visited[201] ={0,}; // 방문 체크

void bfs(int point, vector<vector<int>> computers) {
    queue <int> q;
    visited[point] = 1;
    q.push(point);
    while (!q.empty()) { // bfs
        int x = q.front();
        q.pop();
        for (int i = 0; i < computers[x].size(); i++) {
            if (i != x && !visited[i] && computers[x][i] == 1) { 
            // i!=j(자신의 컴퓨터가 아니고) && 지금까지 방문안했고 && 연결되어 있을 때
                q.push(i);
                visited[i] = 1; // 방문처리
            }
        }
    }
}

int solution(int n, vector<vector<int>> computers) {
    int answer = 0;
    for (int i = 0; i < n; i++) {
        if (!visited[i]) { // 방문안했을때
            answer++;
            bfs(i, computers);
        }
    }
    return answer;
}