[C#] 가장 먼 노드

프로그래머스 문제

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

풀이 후기

1. 분석

흔한 BFS랑 DFS. 방문 확인 배열 대신에 거리 배열로 바꾸고, 방문한 노드에 [내 거리 + 1]을 거리 배열에 저장하면 끝.

2. 실행 결과

3. 코드

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

public class Solution {
    public Node[] nodes;
    public int[] visited;
    
    public class Node{
        public int index;
        public List<int> edges = new List<int>();
        
        public Node(int i){
            index = i;
        }
        
        public void AddEdge(int n){
            edges.Add(n);
        }
    }
    
    public int solution(int n, int[,] edge) {
        nodes = new Node[n + 1];
        visited = new int[n + 1];
        
        for(int i = 1; i < n + 1; i++){
            nodes[i] = new Node(i);
        }
        
        for(int i = 0; i < edge.GetLength(0); i++){
            var a = edge[i, 0];
            var b = edge[i, 1];
            nodes[a].AddEdge(b);
            nodes[b].AddEdge(a);
        }
        
        Queue<int> nextNode = new Queue<int>();
        nextNode.Enqueue(1);
        visited[1] = 1;
        int max = -1;
        
        while(nextNode.Count > 0){
            var index = nextNode.Dequeue();
            var node = nodes[index];
            var count = visited[index] + 1;

            foreach(var e in node.edges){
                var edgeToNode = nodes[e];
                
                if(visited[e] == 0){
                    nextNode.Enqueue(e);
                    visited[e] = count;
                    max = count > max ? count : max;
                }
            }
        }

        return visited.Count(i => i == max);
    }
}

코드에서 노드를 전역 배열에서 꺼내오고 넣지 않은 이유는 시간 차이가 있나 궁금해서 이것 저것 시도한 흔적임.