[PS] 네트워크

프로그래머스

문제

- 네트워크(인접 리스트)의 개수 구하기

 

풀이

컴퓨터의 개수 n과 연결 정보가 담긴 2차원 배열 computers가 매개변수로 주어질 때, 네트워크의 개수를 구하는 문제이다.

네트워크 정의가 뭐지.. 하고 입출력을 일일히 확인해봤다 ㅎㅎ;;

computers[i][j]가 1이면 i번 컴퓨터와 j번 컴퓨터가 연결되어 있다는 의미이고

이 연결 고리들이 네트워크 1개이다!

 

만약 연결되어 있지 않은 컴퓨터가 있다면 네트워크 1개를 추가해야 한다.

 

핵심

• i번 컴퓨터와 j번 컴퓨터가 연결되어 있으면 j번 컴퓨터와 i번 컴퓨터도 연결되어 있다. (양방향 연결)
• i번 컴퓨터와 i번 컴퓨터는 항상 연결되어 있다. (자기 자신과의 연결)

위 두 가지를 고려하고, 그래프 탐색을 하면 된다.

 

DFS와 BFS 모두 가능하지만, BFS에 취약해서 BFS로 풀어보았다

코드

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

using namespace std;

void bfs(int start_node, int n, vector<vector<int>>& computers, vector<bool>& visited_nodes) {
    queue<int> q;
    q.push(start_node);
    visited_nodes[start_node] = true;
    
    while (!q.empty()) {
        int current_node = q.front();
        q.pop();
        
        for (int neighbor_node = 0; neighbor_node < n; ++neighbor_node) {
            // 1. 자기 자신(current_node == neighbor_node)이 아니고
            // 2. 연결되어 있고 (computers[current_node][neighbor_node] == 1)
            // 3. 아직 방문하지 않았다면 (!visited_nodes[neighbor_node])
            if (current_node != neighbor_node && computers[current_node][neighbor_node] == 1 && !visited_nodes[neighbor_node]) {
                q.push(neighbor_node);
                visited_nodes[neighbor_node] = true;
            }
        }
    }
}

int solution(int n, vector<vector<int>> computers) {
    int network_count = 0;
    vector<bool> visited_nodes(n, false); 
    
    // 모든 컴퓨터를 순회하며 아직 방문하지 않은 컴퓨터를 찾음
    for (int i = 0; i < n; ++i) {
        if (!visited_nodes[i]) {
            bfs(i, n, computers, visited_nodes);
            network_count++;
        }
    }
    
    return network_count;
}

 

회고

BFS/DFS 문제는 대부분 DFS로 푸는 게 더 편하긴 한 것 같다