[DAY91] Algorithm : Farthest Node

그래프에서 1번 노드로부터 가장 멀리 떨어진 노드의 개수를 구하는 문제다. 가중치가 없는 그래프에서의 최단 거리는 BFS(너비 우선 탐색)를 사용하는 것이 정석이다. 노드(N)와 간선(E)의 개수가 많으므로 인접 리스트를 활용해 $O(N+E)$로 해결해야 한다.

---

❓ 문제 분석

• 목표: 1번 노드에서 출발했을 때, 최단 경로의 길이가 가장 긴 노드들이 몇 개인지 구하기.
• 제약 조건:
  • 노드 개수 $N$: 최대 20,000 / 간선 개수 $E$: 최대 50,000
  • $O(N^2)$인 인접 행렬 방식은 메모리와 시간 효율이 떨어지므로, 인접 리스트 방식을 사용해야 한다.
• 핵심 키워드: "최단 경로", "간선의 개수", "가장 멀리 떨어진"

---

💡 풀이 설계

1. 시도했던 접근 (Approach)

• 최단 거리를 구해야 하므로 한 경로만 깊게 파고드는 DFS보다는, 시작점에서 가까운 순서대로 탐색하는 BFS가 적합하다고 판단했다.

2. 최종 해결책 (Solution)

• 자료구조:
  • vector<vector<int>>: 인접 리스트로 그래프 구현.
  • vector<int> dist: 거리 저장용 배열. 초기값을 -1로 설정하여 방문 여부 확인(Visited Check)과 거리 기록을 동시에 처리한다.
• 예상 시간 복잡도: $O(N + E)$
  • 모든 노드와 간선을 한 번씩 탐색한다.
• 알고리즘 흐름:
  1. 주어진 간선 정보로 양방향 그래프(인접 리스트)를 생성한다.
  2. BFS를 수행하며 각 노드까지의 최단 거리를 dist 배열에 기록한다.
  3. BFS 종료 후, dist 배열을 순회하며 최댓값을 찾고 그 개수를 센다.

---

💻 코드 구현

#include <string>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

int solution(int n, vector<vector<int>> vertex) {
    int answer = 0;

    // 그래프 생성 (Preprocessing)
    vector<vector<int>> graph(n + 1);
    for (auto& v : vertex) {
        graph[v[0]].push_back(v[1]);
        graph[v[1]].push_back(v[0]);
    }

    // BFS 초기화
    // -1은 '아직 방문 안 함'을 의미 (거리와 방문 체크를 동시에)
    vector<int> dist(n + 1, -1);
    queue<int> q;

    dist[1] = 0;
    q.push(1);

    // BFS 탐색
    while (!q.empty()) {
        int current = q.front();
        q.pop();

        for (auto& next : graph[current]) {
            // 아직 방문하지 않은 노드라면 거리 갱신 후 큐에 추가
            if (dist[next] == -1) {
                dist[next] = dist[current] + 1;
                q.push(next);
            }
        }
    }

    // 결과 계산 (Post-processing)
    // 정렬 없이 한 번의 순회로 최댓값과 개수를 동시에 파악
    int maxDist = 0;
    for (int i = 1; i <= n; i++) {
        if (dist[i] > maxDist) {
            maxDist = dist[i];
            answer = 1;
        } else if (dist[i] == maxDist) {
            answer++;
        }
    }

    return answer;
}

---

🐛 시행착오 및 디버깅

• 초기화 전략: 별도의 bool visited 배열을 두지 않고, 거리 배열 dist를 -1로 초기화하여 방문 여부까지 한 번에 처리함으로써 메모리와 로직을 간소화했다.
• 최댓값 찾기: 결과를 구할 때 sort를 사용하면 $O(N \log N)$이 되지만, 단순 순회를 하면 $O(N)$으로 처리가 가능하다. 데이터가 클 때는 이런 사소한 차이도 중요할 수 있다.

---

✅ 오늘의 회고

항목	내용
유형	그래프 탐색 (Graph), BFS
체감 난이도	하 (BFS의 기본 구조를 묻는 문제)
복잡도	시간: $O(N + E)$, 공간: $O(N)$
새로 배운 것	dist 배열의 초기값을 활용해 방문 체크 배열을 생략하는 테크닉과, Post-processing 단계에서 정렬 대신 순회를 선택해 효율성을 챙기는 습관.