프로그래머스 - 가장 먼 노드 (C#)

문제 설명

n개의 노드가 있는 그래프가 있고, 1번 노드에서 가장 멀리 떨어진 노드가 몇 개인지 구하는 문제입니다.

문제 풀이

노드와 노드 사이의 거리가 모두 1로 동일합니다. 거리에 가중치가 없기 때문에 BFS 알고리즘을 이용해서 풀 수 있습니다.

제출 코드

using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;

public class Solution 
{
    int[,] matrix;
        
    public int solution(int n, int[,] edge) 
    {
        matrix = new int[n + 1, n + 1];
        
        for (int i = 0; i < edge.GetLength(0); i++)
        {
            matrix[edge[i, 0], edge[i, 1]] = 1;
            matrix[edge[i, 1], edge[i, 0]] = 1;
        }        
        
        List<int> counts = new List<int>(BFS(1));
        
        int max = counts.Max();
        int count = counts.Count(val => val == max);

        return count;
    }
    
    public int[] BFS(int start)
    {
        Queue<int> queue = new Queue<int>();
        queue.Enqueue(start);
        
        bool[] isFound = new bool[matrix.GetLength(0)];
        isFound[start] = true;
        
        int[] distance = new int[matrix.GetLength(0)];
        distance[start] = 0;

        while (queue.Count > 0)
        {
            int now = queue.Dequeue();
            
            for (int next = 1; next < matrix.GetLength(0); next++)
            {
                if (matrix[now, next] == 0)
                    continue;
                if (isFound[next])
                    continue;

                queue.Enqueue(next);
                isFound[next] = true;
                
                distance[next] = distance[now] + 1;
            }
        }
        
        return distance;
    }
}