[C#]프로그래머스/네트워크/그래프,DFS

 

using System;
using System.Collections.Generic;
 
public class Solution
{
    public class Node
    {
        public int Value;
        public HashSet<Node> Neighbors;
 
        public Node(int value)
        {
            Value = value;
            Neighbors = new HashSet<Node>();
        }
 
        public void AddNeighbor(Node neighbor)
        {
            Neighbors.Add(neighbor);
        }
    }
 
    public class Graph
    {
        public Dictionary<int, Node> Nodes;
 
        public Graph()
        {
            Nodes = new Dictionary<int, Node>();
        }
 
        public void AddNode(int value)
        {
            if (!Nodes.ContainsKey(value))
                Nodes.Add(value, new Node(value));
        }
 
        public void AddEdge(int fromValue, int toValue)
        {
            Node fromNode = Nodes[fromValue];
            Node toNode = Nodes[toValue];
 
            if (!fromNode.Neighbors.Contains(toNode))
                fromNode.AddNeighbor(toNode);
 
            if (!toNode.Neighbors.Contains(fromNode))
                toNode.AddNeighbor(fromNode);
        }
    }
 
    public int solution(int n, int[,] computers)
    {
        Graph graph = new Graph();
        bool[] visited = new bool[n];
 
        for (int i = 0; i < computers.GetLength(0); i++)
        {
            for (int j = i; j < computers.GetLength(1); j++)
            {
                //연결된 노드만 추가하면 된다.
                //연결안된 노드는 네트워크에 포함이 안되어있으니 정답을 구할 때 필요가 없음
                if (computers[i, j] == 1)
                {
                    graph.AddNode(i);
                    graph.AddNode(j);
                    graph.AddEdge(i, j);
                }
            }
        }
        int answer = 0;
 
        for (int i = 0; i < n; i++)
        {
            //방문한 노드라면 넘어감.
            if (visited[i])
                continue;
 
            answer++;
 
            //해당 노드와 연결된 노드들을 모두 방문한 리스트에 추가한다.
            DFS(graph, visited, i);
        }
 
        return answer;
    }
 
    private void DFS(Graph graph, bool[] visited, int currentNodeValue)
    {
        if (visited[currentNodeValue])
            return;
 
        visited[currentNodeValue] = true;
        Node currentNode = graph.Nodes[currentNodeValue];
 
        //인접 노드들을 검색해서 방문리스트에 추가한다.
        //네트워크 = 인접한 노드들의 묶음
        foreach (Node neighbor in currentNode.Neighbors)
            DFS(graph, visited, neighbor.Value);
    }
}