프로그래머스, C++) Lv 3. 네트워크

문제

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

프로그래머스

 

DFS / BFS 둘다 가능

 

DFS 버전

#include <string>
#include <vector>
using namespace std;

void dfs(int node, vector<vector<int>>& computers, vector<bool>& visited, int n) {
    visited[node] = true;  // 현재 노드 방문 표시

    for (int i = 0; i < n; i++) {
        // 자기 자신이 아니면서, 연결되어 있고, 아직 방문 안 한 경우
        if (i != node && computers[node][i] == 1 && !visited[i]) {
            dfs(i, computers, visited, n);  // 연결된 노드로 재귀 호출
        }
    }
}

int solution(int n, vector<vector<int>> computers) {
    int answer = 0;
    vector<bool> visited(n, false);  // 방문 여부 배열 초기화

    for (int i = 0; i < n; i++) {
        // 아직 방문하지 않은 노드라면, 새로운 네트워크 시작
        if (!visited[i]) {
            dfs(i, computers, visited, n);
            answer++;  // DFS 하나 끝날 때마다 새로운 네트워크 발견
        }
    }

    return answer;
}

 

BFS 버전 - queue 사용

#include <string>
#include <vector>
#include <queue>
using namespace std;

void bfs(int start, vector<vector<int>>& computers, vector<bool>& visited, int n) {
    queue<int> q;
    q.push(start);
    visited[start] = true;  // 시작 노드 방문 표시

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

        for (int i = 0; i < n; i++) {
            // 자기 자신이 아니고, 연결되어 있으며, 아직 방문하지 않았다면
            if (i != node && computers[node][i] == 1 && !visited[i]) {
                visited[i] = true;
                q.push(i);  // 다음으로 탐색할 노드를 큐에 추가
            }
        }
    }
}

int solution(int n, vector<vector<int>> computers) {
    int answer = 0;
    vector<bool> visited(n, false);

    for (int i = 0; i < n; i++) {
        if (!visited[i]) {
            bfs(i, computers, visited, n);
            answer++;  // BFS 한 번 끝날 때마다 새로운 네트워크 발견
        }
    }

    return answer;
}