🌞문제

🌞접근법

n개의 노드가 있는 그래프가 있다. 이 떄, 각 노드는 1~n까지의 번호가 적혀있다.
1번 노드에서 가장 멀리 떨어진 노드의 갯수를 구하려고 한다.

가장 멀리 떨어진 노드 = 최단경로를 이동했을 때 간선의 개수가 가장 많은 노드를 의미한다.

노드의개수 = n, 간선에 대한 정보가 담긴 2차원배열 vertex

구해야 하는 값 : 1번 노드로부터 가장 멀리 떨어진 노드의 개수

조건1. 노드의 개수 = n~2만
조건2. 간선은 양방향이며 1~5만개

첫번째 시도방법
0. 먼저 해시테이블에 key를 부모노드로, 값을 자식노드로하여 저장을한다. (양방향 그래프 이므로, 양쪽 방향으로 해주어야 한다.)
1. 1번 노드부터 dfs탐색을 하면서 어떠한 노드에 도착 했을 때, 몇 개의 간선을 지나쳐 왔는지를 cnt에 저장하고, 그 값을 배열에 유지한다.
2. 배열을 유지 할 때, 최소 경로의 cnt를 유지해야 하므로, cnt 값을 구했다면 현재 저장된 값과 비교를 통하여 값이 작은 것으로 대체한다.
3. 하나의 dfs당 하나의 visit배열을 두어서 사이클을 방지한다.
4. 마지막으로 간선의 이동횟수를 저장한 배열을 내림차순으로 sort하여, 첫번째 값과 같은 요소를 찾아서 answer 값을 증가 시킨다.

첫번째 방법이 실패를 했다.
이유는 dfs로 풀 경우 시간초과가 발생한다. n이 1만 일때는 dfs를 사용해서는 안된다는 것을 배웠다.
그래서 dfs를 bfs로 변경하고 문제를 풀어주었다.

🌞풀이

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

using namespace std;

int min_move[20001];
unordered_map<int, vector<int>> vertex;
int visit[20001];

void bfs()
{
    visit[1] = 1;
    queue<int> q;
    q.push(1);
    while(!q.empty())
    {
        int parent = q.front();
        q.pop();
        
        for(int i=0;i<vertex[parent].size();i++)
        {
            int child = vertex[parent][i];
            if(visit[child] == 0)
            {
                q.push(child);
                visit[child] = 1;
                min_move[child] = min_move[parent]+1;
            }
        }
    }
}


int solution(int n, vector<vector<int>> edge) {
    int answer = 0;
    
    for(int i=0;i<edge.size();i++)
    {
        int first = edge[i][0];
        int second = edge[i][1];

        if(vertex.find(first) == vertex.end())
        {
            vector<int> v;
            v.push_back(second);
            vertex.insert(make_pair(first,v));
        }
        
        else
        {
            vertex[first].push_back(second);
        }
        
        if(vertex.find(second) == vertex.end())
        {
            vector<int> v;
            v.push_back(first);
            vertex.insert(make_pair(second,v));
        }
        else
        {
            vertex[second].push_back(first);
        }
    }
    
    bfs();
    

    int max = -2147483640;
    
    for(int i=1;i<n+1;i++)
    {
        if(max < min_move[i]) max = min_move[i];
    }
    
    for(int i=1;i<n+1;i++)
    {
        if(max == min_move[i]) answer++;
    }
    
    return answer;
}