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

문제

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

---

풀이

1. 노드의 개수 n, 간선 정보 computers 벡터가 주어졌을 때 간선으로 이어진 덩어리의 개수를 세는 문제이다. => bfs로 풀이

2. 이중벡터로 간선 정보를 포함한 인접 리스트를 만든다.

3. 인접 리스트를 순회하며 방문하지 않은 노드를 bfs 큐에 넣어주고, 방문 표시를 해준다.
   3-1. bfs 큐가 빌 때(간선으로 이어진 모든 노드를 탐색할 때)까지 간선으로 이어진 다음 노드를 탐색하고, 3을 수행한다.
   3-2. bfs 큐가 비었다면, 한 덩어리를 모두 탐색했다는 뜻이기에 개수를 증가시킨다.

---

코드

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

using namespace std;

int solution(int n, vector<vector<int>> computers) 
{
    vector<vector<int>> adj(n);
    for (int i=0; i<computers.size(); i++)
    {
        for(int j =0; j<computers[i].size(); j++)
        {
            if(i == j || computers[i][j] == 0)
                continue;

            adj[i].push_back(j);
        }
    }
    
    queue<int> bfs;
    vector<bool> visited(n, false);
    
    int answer = 0;
    
    for(int i=0; i<adj.size(); i++)
    {
        if (visited[i])
            continue;
        
        bfs.push(i);
        visited[i] = true;
        
        while (!bfs.empty())
        {
            int current = bfs.front();
            bfs.pop();
        
            for (int next : adj[current])
            {
                if (visited[next])
                    continue;
                
                visited[next] = true;
                bfs.push(next);
            }
        }
        
        answer++;
    }
    
    return answer;
}

---

다른 풀이와 코드

0. dfs를 사용한 코드

1. bfs보다 코드가 짧아서 가독성이 좋다. 다만 개인적으로 재귀함수 사용이 미숙해서 dfs는 꺼리게 되는듯..

#include <string>
#include <vector>

using namespace std;

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

int solution(int n, vector<vector<int>> computers) 
{
    int network = 0;
    vector<int> visited(n, 0);

    for (int i = 0; i <n; i++) 
    {
        if (visited[i] == 1) 
        {
            continue;
        }

        // visit node and start DFS
        network++;
        visited[i] = 1;

        DFS(i, n, visited, computers);
    }

    return network;
}