프로그래머스 레벨3 가장 먼 노드 C#(JAVA) queue, BFS

C#(다른 분 거를 참조했다)

 

 

 

 

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;
    }
}

 

 

 

 

//////////////

 

 

 

자바

 

 

 

import java.util.*;

class Solution {
    public int solution(int n, int[][] edge) {
        int[] dist = new int[n+1];
        boolean[][] map = new boolean[n+1][n+1];
        
        for(int i =0; i<edge.length; i++)
        {
            map[edge[i][1]][edge[i][0]] = map[edge[i][0]][edge[i][1]]= true;
        }

        LinkedList<Integer> que = new LinkedList<Integer>();
        que.add(1);

        while(!que.isEmpty())
        {
            int temp = que.pollFirst();
            
            for(int i = 2; i<n+1; i++)
            {
                if(map[temp][i]&&dist[i]==0)
                {
                    que.addLast(i);
                    dist[i] = dist[temp]+1;
                }
            }
        }

        Arrays.sort(dist);
        int i = dist.length-1;
        
        for(; i>0; --i)
        {
            if(dist[i]!=dist[i-1])
            {
                break;
            }
        }

        return dist.length-i;
    }
}