[프로그래머스 C#] Lv.3 네트워크

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

프로그래머스

1. 정답코드 및 핵심 아이디어, 유의사항

연결된 컴퓨터들의 묶음을 하나의 네트워크로 보고 네트워크의 개수를 구하는 문제

 

- 0번 컴퓨터부터 끝까지 체크하여 네트워크에 연결됨을 파악한 컴퓨터인지 판단

- 만약 새로운 네트워크를 발견했다면 해당하는 네트워크 내의 모든 컴퓨터를 탐색 (BFS 탐색)

 

BFS 알고리즘

https://godgjwnsgur7.tistory.com/47

[Algorithm C#] BFS, DFS ( + Back Tracking )

 

주석 참조

    using System;
    using System.Collections.Generic;

    public class Solution
    {
        public int solution(int n, int[,] computers)
        {
            int answer = 0; // 네트워크 개수
            var boolArray = new bool[n]; // 방문배열 : 네트워크에 연결된 컴퓨터인지?
            var queue = new Queue<int>(); // BFS 탐색대상 Queue

            for (int i = 0; i < n; i++)
            {
                // 이미 연결된 컴퓨터라면
                if (boolArray[i] == true)
                    continue;

                // 새로운 네트워크 발견
                answer++;
                boolArray[i] = true;
                queue.Enqueue(i);

                // 연결된 모든 네트워크 탐색 (BFS)
                while (queue.Count > 0)
                {
                    int index = queue.Dequeue();

                    for (int j = 0; j < n; j++)
                    {
                        // 아직 연결이 파악되지 않은 연결된 컴퓨터 발견
                        if (boolArray[j] == false && computers[index, j] == 1)
                        {
                            queue.Enqueue(j);
                            boolArray[j] = true;
                        }
                    }
                }
            }

            return answer;
        }
    }