Programmers_가장 먼 노드

대체로 DFS, BFS 문제들이 난이도에 비해 LV3인 것 같다. 필자는 쉽게 BFS로 풀었다.

• 1번 노드에서 가장 멀리 떨어진 노드의 개수를 구하는 문제.
• BFS로 1번 노드부터 시작해 전체 연결된 노드에 방문한다.
• check 배열로 한번 지나간 노드는 막아준다.
• cost 배열로 1번 노드에서 얼마나 떨어져 있는지 저장한다.
• BFS가 끝나면 cost 배열을 모두 조회하며, 가장 거리가 먼 노드의 수를 찾아낸다.

💻 전체코드

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

using namespace std;

vector<int>v[20001];
bool check[20001];
int cost[20001];

void bfs()
{
    queue<int>q;
    q.push(1);
    check[1] = true;
    while(!q.empty())
    {
        int cur = q.front();
        int curcost = cost[q.front()];
        q.pop();
        for(int i=0;i<v[cur].size();i++)
        {
            if(check[v[cur][i]]) continue;
            check[v[cur][i]] = true;
            cost[v[cur][i]] = curcost + 1;
            q.push(v[cur][i]);
        }
    }
}

int solution(int n, vector<vector<int>> edge) {
    int answer = 0;
    
    for(int i=0;i<edge.size();i++)
    {
        v[edge[i][0]].push_back(edge[i][1]);
        v[edge[i][1]].push_back(edge[i][0]);
    }
    
    bfs();
    
    int maxnum=0;
    
    for(int i=1;i<=n;i++)
    {
        if(maxnum == cost[i]) answer++;
        else if(maxnum < cost[i])
        {
            answer=1;
            maxnum = cost[i];
        }
    }
        
    return answer;
}