[백준] 11724 연결요소 (C#)

문제

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

고민

연결요소란?

그래프를 그릴 때 연결된 요소들의 개수를 말한다.

즉, 노드가 1~6까지 주어졌을 때 그래프를 그려봤더니

1-2-4

3-5

6

이렇게 연결이 되었다고 하자.

그러면 연결요소는 3개다.

 

문제에서 노드가 6개고 간선이 5개인 그래프가 주어졌다. 

아래 연결 정보를 따라 그래프를 그려보면

1 - 2 - 5

3 - 4 - 6

이렇게 이어진다.

그려면 연결요소는 2개다.

 

위 과정으로 로직을 고민해봤다.

1. 인접 요소를 연결한다.

2. 연결이 끝나면 카운트를 한다.

끝이다! 겁나 간단하다.

코드

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace CodingTest.Greedy
{
    internal class BJH
    {
        static int n, m; // 노드, 간선
        static bool[,] adjMatrix; // 그래프
        static bool[] visited; // 방문 여부

        // DFS
        // node를 통해 연결요소를 찾음
        static void DFS(int node)
        {
            visited[node] = true; // 방문처리
            for(int i = 1; i <= n; i++) // 해당 노드와 i가 연결되어 있는지 확인하는 반복문
            {
                if (adjMatrix[node, i] == true && visited[i] == false)
                {
                    DFS(i); // 연결 되어 있으면 다음 노드를 찾아 떠남
                }
            }
        }
        static void Main(string[] args)
        {
            string[] input = Console.ReadLine().Split(' ');
            n = int.Parse(input[0]);
            m = int.Parse(input[1]);

            adjMatrix = new bool[n+1, n+1];
            visited = new bool[n+1];

            for(int i = 0; i < m; i++)
            {
                input = Console.ReadLine().Split(' ');
                int u = int.Parse(input[0]);
                int v = int.Parse(input[1]);

                adjMatrix[u, v] = true;
                adjMatrix[v, u] = true;
            }

            int cnt = 0;
            for(int i = 1; i <= n; i++)
            {
                if (visited[i] == false)
                {
                    DFS(i);
                    cnt++;
                }
            }
            Console.WriteLine(cnt);
        }
    }
}