[코딩테스트] [프로그래머스] 가장 먼 노드

문제

https://school.programmers.co.kr/learn/courses/30/lessons/49189?language=cpp

---

풀이

1. 간선 정보를 포함한 무방향 그래프를 이중 벡터로 구현한다. 이때, 노드 번호가 1부터 시작이므로 1씩 빼준다.
   1-1. 오름차순으로 노드를 탐색할 수 있도록 정렬해준다.

2. 시작점(0번 노드)를 큐에 넣고, bfs를 수행한다.
   2-1. 거리를 저장할 벡터(distance)를 만들어서, -1로 초기화를 해준다.
   2-2. 만약 다음 노드의 거리가 -1이라면 아직 방문하지 않은 것이기에, 현재 거리 + 1로 설정해준다.
   2-3. 큐가 빌 때까지 반복

3. algorithm 헤더의 max_element로 distance 요소 중 가장 큰 값을 구한다.
   3-1. distance 벡터를 순회하며, 최대 거리와 같은 요소가 있다면 반환할 노드 수를 증가시킨다.

---

코드

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

using namespace std;

int solution(int n, vector<vector<int>> edge) 
{
    vector<vector<int>> adj(n);
    for(int i=0; i<edge.size(); i++)
    {
        int from = edge[i][0];
        int to = edge[i][1];
        
        --from;
        --to;
        
        adj[from].push_back(to);
        adj[to].push_back(from);
    }
    
    for(int i=0; i<adj.size(); i++)
    {
        sort(adj[i].begin(), adj[i].end());
    }
    
    vector<int> distance(n, -1);
    
    queue<int> bfs;
    bfs.push(0);
    distance[0] = 0;

    while(!bfs.empty())
    {
        int current = bfs.front();
        bfs.pop();
        
        for(int next : adj[current])
        {
            if(distance[next] != -1)
                continue;
            
            distance[next] = distance[current] + 1;
            bfs.push(next);
        }
    }
    
    int answer = 0;
    int maxDistance = *max_element(distance.begin(), distance.end());
    
    for(int i =0; i<distance.size(); i++)
    {
        if(distance[i] == maxDistance)
            answer++;
    }
    
    return answer;
}