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

프로그래머스

문제 요약

1번 노드에서 가장 멀리 떨어진 노드 찾기

접근

1. 그래프 탐색

BFS로 탐색하면 1에서부터 각 노드마다의 거리가 나온다.
가장 마지막 구해진 거리(가장 먼 거리)와 같은 개수를 구하면 된다.

max_dist = max(max_dist, visit[adj]);

• 모든 노드를 탐색할때 가장 큰 값을 저장해놓고

  int ret = 0;
  for (auto v:visit)
  {
    if (v == max_dist) ret++;
  }
  return ret;

• 해당 값을 사용해서 같은 거리인 노드의 개수를 센다.

전체 코드

#include <string>
#include <vector>
#include <queue>
#include <algorithm> // max
using namespace std;

int bfs(int start, int size, const vector<vector<int>>& adj_list)
{
    int max_dist = 0;
    vector<int> visit(size+1, 0);

    queue<int> q;
    q.push(start);

    visit[start] = 1;
    while(!q.empty())
    {
        int cur = q.front();
        q.pop();

        for (auto adj: adj_list[cur])
        {
            if (visit[adj]) continue;
            visit[adj] = visit[cur] + 1;
            max_dist = max(max_dist, visit[adj]);
            q.push(adj);
        }
    }

    int ret = 0;
    for (auto v:visit)
    {
        if (v == max_dist) ret++;
    }
    return ret;
}

int solution(int n, vector<vector<int>> edge) {
    int answer = 0;
    vector<vector<int>> adj_list(n+1);
    for (auto edg:edge) 
    {
        adj_list[edg[0]].push_back(edg[1]);
        adj_list[edg[1]].push_back(edg[0]);
    }

    answer = bfs(1, n, adj_list);
    return answer;
}