[프로그래머스] 가장 먼 노드(C++)

문제 링크

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

프로그래머스

 

 

코드 구현

#include <iostream>
#include <vector>
#include <string>
#include <queue>

using namespace std;

vector<vector<int>> graph;
vector<int> visited;
queue<int> q;

void bfs(int start)
{
    visited[start] = 1;
    q.push(1);

    while (!q.empty())
    {
        int now = q.front();
        q.pop();

        for (int neighbor : graph[now])
        {
            if (!visited[neighbor])
            {
                visited[neighbor] = 1 + visited[now];
                q.push(neighbor);
            }
        }
    }

}

int solution(int n, vector<vector<int>> edge) 
{
    int answer = 0;
    graph.resize(n + 1);
    visited.resize(n + 1, 0);

    // 그래프 생성
    for (int i = 0; i < edge.size(); i++)
    {
        int node = edge[i][0];
        int neighbor = edge[i][1];

        graph[node].push_back(neighbor);
        graph[neighbor].push_back(node);
    }

    bfs(1);

    // 최단 경로 = 최댓값
    int maxValue = 0;
    if (!visited.empty())
    {
        maxValue = *max_element(visited.begin(), visited.end());
    }

    // 최단 경로 개수 구하기
    answer = count(visited.begin(), visited.end(), maxValue);

    return answer;
}

 

 

해결 방법

우선 최단 경로를 찾아야 하므로 bfs로 문제를 접근했고, 한 노드에서 이웃 노드로 이동할 때마다 이전 노드의 값 + 1을 더해주어 거리를 계산하였다. bfs 함수가 끝나면 숫자가 가장 큰 노드가 가장 멀리 떨어져 있는 노드이므로 가장 큰 숫자를 가지고 있는 노드의 개수를 세어주면 된다.