프로그래머스 - 네트워크 (C#)

문제 설명

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

A컴퓨터와 B컴퓨터와 C컴퓨터가 연결되어 있을 때 네트워크의 개수는 1개입니다.
A컴퓨터와 B컴퓨터가 연결되어 있고, C컴퓨터와 D컴퓨터가 연결되어 있을 때 네트워크의 개수는 2개입니다.

문제 풀이

매개변수로 받은 연결된 목록들을 그래프 형태로 만듭니다.
첫 컴퓨터(i)부터 첫 컴퓨터와 연결된 모든 컴퓨터들(j)을 BFS로 찾아냅니다.
그리고 찾은 컴퓨터들은 전부 검색에서 제외시킬 정수형 List에 담습니다.
찾은 컴퓨터들은 이미 연결된 컴퓨터가 있다는 것을 알기 때문에 확인할 필요가 없습니다.

반복문을 돌릴 때 제외시킨 List에 포함되어 있지 않으면
또 다른 네트워크가 있다는 것으로 보고 count를 올립니다.

제출 코드

using System;
using System.Collections;
using System.Collections.Generic;

public class Solution 
{
    public int solution(int n, int[,] computers) 
    {
        int answer = 0;

        int[,] graph = new int[n, n];
        
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < n; j++)
            {
                graph[i, j] = computers[i, j];
            }
        }
        
        int count = 0;
        
        List<int> include = new List<int>();
        
        for (int i = 0; i < n; i++)
        {
            if (include.Contains(i)) continue;
            
            count++;
            include.Add(i);
            
            Queue<int> queue = new Queue<int>();
            queue.Enqueue(i);
            
            while (queue.Count > 0) // i와 연결된 모든 네트워크 찾기
            {
                int now = queue.Dequeue();
                
                for (int j = 0; j < n; j++)
                {
                    if (now == j) continue;
                    if (include.Contains(j)) continue;
                    
                    if (graph[now, j] == 1)
                    {
                        include.Add(j);
                        queue.Enqueue(j);
                    }
                }
            }
        }

        answer = count;
        
        return answer;
    }
}