<Lv.3> 네트워크 (프로그래머스 : C#)

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

📕 문제 설명

컴퓨터 개수와 컴퓨터 연결 정보가 주어질 때 네트워크 개수 반환
(서로 이어진 컴퓨터를 하나의 네트워크에 있다고 본다.)

computer[i][j] = 1 : 컴퓨터 i와 j가 연결되어 있음

• Input
  컴퓨터 개수 n, 컴퓨터 연결 정보
• Output
  네트워크 개수

예제

풀이

visited 배열로 방문한거 체크해둔 후 새롭게 만들어지는 네트워크에 대해서만 1씩 count 증가시키기

using System;
using System.Collections.Generic;

public class Solution {
    public int solution(int n, int[,] computers) {
        int answer = 0;
        List<int>[] adjList = new List<int>[n];
        for (int i = 0; i < computers.GetLength(0); i++)
        {
            adjList[i] = new List<int>();
        }
        
        for (int i = 0; i < computers.GetLength(0); i++) // 인접 리스트 만들기
        {
            for (int j = 0; j < n; j++)
            {
                if (i == j) continue;
                if (computers[i, j] == 1)
                {
                    adjList[i].Add(j);
                }
            }
        }
        
        bool[] visited = new bool[n]; 
        
        for (int i = 0; i < n; i++)
        {
            if (!visited[i])
            {
                answer += FindNetwork(i, adjList, visited);
            }
        }
        
        return answer;
    }
    
    private int FindNetwork(int currComputer, List<int>[] adjList, bool[] visited)
    {
        visited[currComputer] = true;
        for (int i = 0; i < adjList[currComputer].Count; i++)
        {
            int adjComputer = adjList[currComputer][i];
            if (!visited[adjComputer])
            {
                FindNetwork(adjComputer, adjList, visited);
            }
        }
        
        return 1;
    }
}

결과