[프로그래머스 C#] Lv.3 가장 먼 노드

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

프로그래머스

1. 정답코드 및 핵심 아이디어, 유의사항

1번 노드로부터 가장 멀리 떨어진 노드의 개수를 구하는 문제

- 1번에서부터 BFS 알고리즘으로 탐색하며 각 노드와 1번 노드의 최단거리를 구함

- 정점과 간선으로 봤을 때, 이어진 두 정점의 가중치(거리)는 무조건 1

 

BFS 탐색 중에 최단거리가 세팅되지 않은 노드를 탐색하게 되면 최단거리를 세팅

- 이동할 노드의 최단거리 = 이전 노드의 최단거리 + 1

+ 초기 1번 노드의 최단거리는 무조건 0이며, 1번 노드로 다시 이동하지 않도록 처리

 

BFS 알고리즘

https://godgjwnsgur7.tistory.com/47

[Algorithm C#] BFS, DFS ( + Back Tracking )

주석 참조

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

    public class Solution
    {
        public int solution(int n, int[,] edge)
        {
            int answer = 0;
            var intArray = new int[n + 1]; // 1번과의 최단거리 배열
            var dict = new Dictionary<int, List<int>>(); // 노드그래프

            // 노드그래프 세팅
            for (int i = 1; i <= n; i++)
                dict.Add(i, new List<int>());

            for (int i = 0; i < edge.GetLength(0); i++)
            {
                dict[edge[i, 0]].Add(edge[i, 1]);
                dict[edge[i, 1]].Add(edge[i, 0]);
            }
            
            // 1번 노드에서부터 BFS 탐색 시작
            var queue = new Queue<int>();
            queue.Enqueue(1);

            // BFS 탐색 : 각 노드에 1번과의 최단거리 세팅
            while (queue.Count > 0)
            {
                int currNode = queue.Dequeue();

                foreach (int moveNode in dict[currNode])
                {
                    // 시작점으로 돌아오지 않도록
                    if (moveNode == 1)
                        continue;

                    // 최단거리 세팅이 되지 않은 노드
                    if (intArray[moveNode] == 0)
                    {
                        intArray[moveNode] = intArray[currNode] + 1; // 이동
                        queue.Enqueue(moveNode);
                    }
                }
            }

            // 가장 먼 거리를 받아와 개수를 카운트
            int maxDir = intArray.Max();
            foreach (int num in intArray)
                if (num == maxDir)
                    answer++;

            return answer;
        }
    }