[BOJ/C#] 11724 연결 요소의 개수

https://www.acmicpc.net/problem/11724

11724번: 연결 요소의 개수

 

 

1단계 

using System;
using System.IO;
using System.IO.Pipes;
using System.Text;

namespace Assignment01
{
    class Program
    {
        static void Main(string[] args)
        {
            int[] nm = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);
            //n : 정점의 개수, m : 간선의 개수
            // 1<= n <= 1000
            // 0 <= m <= n x (n-1)/2
            //m개의 줄에 양 끝점 u, v
            //1 ≤ u, v ≤ N, u ≠ v
            int n = nm[0];
            int m = nm[1];

            int[,] arr = new int[1000,1000];
                
            for (int i = 0; i < m; i++)
            {
                int[] uv = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);
                int u = uv[0];  //x
                int v = uv[1];  //y
                arr[u, v] = 1;
                arr[v, u] = 1;
            }

            for (int x = 0; x < m+1; x++)
            {
                for (int y = 0; y < m+1; y++)
                {
                    Console.Write("{0} ", arr[x,y]);
                }
                Console.WriteLine();
            }
        }
    }
}

---

 

 

2단계 

 

using System;
using System.Collections.Generic;
using System.IO;
using System.IO.Pipes;
using System.Text;

namespace Assignment01
{
    class Program
    {
        private const int MAX = 1001;
        private static int[] visited = new int[MAX];
        private static int n;
        private static int[,] map;
        
        static void Main(string[] args)
        {
            int[] nm = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);
            //n : 정점의 개수, m : 간선의 개수
            // 1<= n <= 1000
            // 0 <= m <= n x (n-1)/2
            //m개의 줄에 양 끝점 u, v
            //1 ≤ u, v ≤ N, u ≠ v
            n = nm[0];
            int m = nm[1];

            map = new int[MAX,MAX];
                
            for (int i = 0; i < m; i++)
            {
                int[] uv = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);
                int u = uv[0];  //x
                int v = uv[1];  //y
                map[u, v] = 1;
                map[v, u] = 1;
            }

            // for (int u = 0; u < m+1; u++)
            // {
            //     for (int v = 0; v < m+1; v++)
            //     {
            //         Console.Write("{0} ", map[u,v]);
            //     }
            //     Console.WriteLine();
            // }
            
            //2단계 
            int cnt = 0;
            
            //u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 이므로 1부터 시작  
            for (int i = 1; i < n; i++)
            {
                if (visited[i] == 0)    //방문 하지 않았다면 
                {
                    //BFS(i);
                    //DFS(i);
                    cnt++;
                    DFSRecur(i);
                    
                }
            }
            
            Console.WriteLine("{0}", cnt);
        }

        static void DFSRecur(int v)
        {
            visited[v] = 1;
            for (int u = 1; u <= n; u++)
            {
                if(map[v,u] == 1 && visited[u] == 0)
                    DFSRecur(u);
            }
        }

        static void DFS(int v)
        {
            Stack<int> q = new Stack<int>();
            q.Push(v);   //큐에 넣고 
            visited[v] = 1; //방문 체크 하고 


            while (q.Count > 0)
            {
                v = q.Pop();

                for (int u = 0; u <= n; u++)
                {
                    //간선이 있고, 방문 하지 않았다면 
                    if (map[v, u] == 1 && visited[u] == 0)
                    {
                        q.Push(u);
                        visited[u] = 1; 
                    }
                }
            }
        }
        
        
        static void BFS(int v)
        {
            Queue<int> q = new Queue<int>();
            q.Enqueue(v);   //큐에 넣고 
            visited[v] = 1; //방문 체크 하고 


            while (q.Count > 0)
            {
                v = q.Dequeue();

                for (int u = 0; u <= n; u++)
                {
                    //간선이 있고, 방문 하지 않았다면 
                    if (map[v, u] == 1 && visited[u] == 0)
                    {
                        q.Enqueue(u);
                        visited[u] = 1; 
                    }
                }
            }
        }
    }
}

 

BFS : Queue

DFS : Stack