1. 문제 정의

그래프의 시작점인 1번 노드에서 가장 멀리 떨어진 노드의 개수를 구하는 문제.
최단경로 기준으로 가장 많은 간선을 거쳐야 도달하는 노드들의 개수를 반환.

2. 문제 접근 방식

그래프 표현:
인접 리스트를 사용하여 각 노드와 연결된 노드 정보를 저장.
양방향 간선이므로, 서로 연결된 두 노드 모두를 저장.
최단경로 탐색:
BFS(너비 우선 탐색)를 사용하여 최단 경로를 탐색.
시작 노드에서 각 노드까지의 거리(distances)를 계산.
가장 먼 거리 계산:
distances 배열에서 최댓값을 찾아 해당 거리와 같은 노드들의 개수를 구함.

3. 코드 설명

import Foundation

func solution(_ n: Int, _ edge: [[Int]]) -> Int {
    // 1. 그래프 생성
    var graph = Array(repeating: [Int](), count: n + 1)
    for e in edge {
        let a = e[0]
        let b = e[1]
        graph[a].append(b)
        graph[b].append(a)
    }
    
    // 2. BFS 초기화
    var distances = Array(repeating: -1, count: n + 1)  // 거리 저장
    var queue = [1]  // 시작 노드는 1
    distances[1] = 0  // 시작 노드의 거리는 0으로 설정
    
    // 3. BFS 탐색
    while !queue.isEmpty {
        let current = queue.removeFirst()
        
        for neighbor in graph[current] {
            if distances[neighbor] == -1 {  // 아직 방문하지 않은 노드
                distances[neighbor] = distances[current] + 1
                queue.append(neighbor)
            }
        }
    }
    
    // 4. 가장 먼 거리 계산
    let maxDistance = distances.max()!
    return distances.filter { $0 == maxDistance }.count
}

4. 핵심 구현 포인트

그래프 생성:
Array(repeating: Int, count: n + 1)로 빈 배열을 초기화.
for e in edge에서 양방향 간선 관계를 추가.
결과적으로 각 노드에 연결된 노드들을 배열 형태로 저장.

BFS로 최단 거리 계산:
queue를 사용하여 탐색할 노드를 관리.
distances 배열은 시작 노드에서 다른 노드까지의 거리를 저장.
BFS의 특징인 최단 경로 탐색을 활용해 모든 노드의 거리를 계산.

가장 먼 거리의 노드 개수 계산:
distances.max()로 가장 먼 거리 값을 구함.
distances.filter { $0 == maxDistance }.count로 해당 거리 값을 가진 노드의 개수를 반환.

5. 입출력 예시

입력:
let n = 6
let edge = [[3, 6], [4, 3], [3, 2], [1, 3], [1, 2], [2, 4], [5, 2]]

출력:
let result = solution(n, edge) // 3

과정:
그래프 표현:
graph = [
[], // 0번 노드는 사용하지 않음
[3, 2], // 1번 노드
[3, 1, 4, 5], // 2번 노드
[6, 4, 2, 1], // 3번 노드
[3, 2], // 4번 노드
[2], // 5번 노드
[3] // 6번 노드
]

BFS 거리 계산:
distances = [-1, 0, 1, 1, 2, 2, 2]

결과:
가장 먼 거리(maxDistance) = 2
해당 거리의 노드: 4, 5, 6 (총 3개)

6. 느낀 점

BFS의 효율성:
BFS는 그래프의 모든 노드를 한 번씩 방문하며, 최단 경로를 구하는 데 매우 적합하다.
그래프 표현 방식:
인접 리스트를 사용하면 메모리 효율적이며, 노드 간의 연결 정보를 효과적으로 표현할 수 있다.
테스트 케이스 설계:
간선이 많은 경우와 적은 경우, 다양한 그래프 구조를 테스트하며 정확성을 검증해야 한다.