<Lv.3> 가장 먼 노드 (프로그래머스 : C#)

https://school.programmers.co.kr/learn/courses/30/lessons/49189

📕 문제 설명

1번 노드에서 가장 멀리 떨어진 노드 개수 구하기

가장 멀리 떨어진 노드란 최단 경로로 이동 시 간선 개수가 가장 많은 노드를 말한다.

• Input
  노드 개수 n, 간선 정보 vertex
• Output
  1번 노드로부터 가장 멀리 떨어진 노드 개수

예제

풀이

BFS로 전체 그래프 순회해서 마지막 층일때 개수 반환하기

using System;
using System.Collections.Generic;

public class Solution {
    public int solution(int n, int[,] edge) {
        int answer = 0;
        
        List<int>[] graph = new List<int>[n+1];
        bool[] visited = new bool[n+1];
        
        for (int i = 0; i < n+1; i++)
        {
            graph[i] = new List<int>();
        }
        
        for (int i = 0; i < edge.GetLength(0); i++) // 양방향 그래프 초기화 
        {
            int firstNode = edge[i,0];
            int secondNode = edge[i,1];
            graph[firstNode].Add(secondNode);
            graph[secondNode].Add(firstNode);
        }
        
        Queue<(int, int)> queue = new Queue<(int, int)>();
        queue.Enqueue((1, 0));
        visited[1] = true;
        int maxDistance = 0;
        
        // BFS -> 마지막 층이 정답
        while (queue.Count >= 1)
        {
            (int currNode, int currDistance) = queue.Dequeue();
            List<int> adjList = graph[currNode];
            
            if (currDistance > maxDistance) // max distance 갱신
            {
                answer = 0;
                maxDistance = currDistance;
            }

            if (maxDistance == currDistance) // 같은 층이면 개수 세기 
            {
                answer += 1;
            }
            
            foreach(int adjNode in adjList)
            {
                if (!visited[adjNode])
                {
                    visited[adjNode] = true; 
                    queue.Enqueue((adjNode, currDistance + 1));
                }
            }
        }
        
        
        return answer;
    }
    
}

결과