Programmers / BFS, DFS / 네트워크

< 문제링크 >

https://www.welcomekakao.com/learn/courses/30/lessons/43162

< 풀이 >

1. 0번 컴퓨터 부터 시작하면서 0번 컴퓨터와 연결된 모든 컴퓨터를 찾아낸다.

2. 찾아낸 컴퓨터들을 방문했다고 체크하고, 네트워크 수를 1 증가 시킨다.

3. 방문하지 않은 컴퓨터가 없을 때까지 반복한다.

< 코드 >

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

int solution(int n, vector<vector<int>> computers) {
    int answer = 0;
    // 해당 컴퓨터가 네트워크 확인에 쓰였는가
    vector<bool> visited(n);
    queue<int> que;
    for (int i = 0; i < n; i++) {
        // 이미 조사한 컴퓨터는 패스
        if (visited[i]) continue;
        que.push(i);
        visited[i] = true;
        // 해당 컴퓨터와 연결된 모든 컴퓨터를 찾아냄
        while (!que.empty()) {
            int cur = que.front();
            que.pop();
            for (int j = 0; j < n; j++) {
                if (visited[j]) continue;
                // 현재 컴퓨터와 연결된 컴퓨터를 모두 queue에 추가
                if (computers[cur][j]) {
                    que.push(j);
                    visited[j] = true;
                }
            }
        }
        answer++;
    }
    return answer;
}

< DFS 함수로 분리한 코드 >

#include <string>
#include <vector>

using namespace std;

void DFS(int from, int n, vector<bool> &visited, vector<vector<int>> computers)
{
    for (int i = 0; i < n; i++) {
        if (visited[i]) continue;
        if (!visited[i] && computers[from][i]) {
            visited[i] = true;
            DFS(i, n, visited, computers);
        }
    }
}

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]) continue;
        // 네트워크 구조 탐색
        answer++;
        visited[i] = true;
        DFS(i, n, visited, computers);
    }
    return answer;
}