<Programmers> Graph, BFS_가장 먼 노드 c++

Lv3. 가장 먼 노드

💡Idea

• 주어진 양방향 간선을 인접 리스트 그래프로 만들어 준다
• 시작 정점 1에서부터 인접한 노드들 중 방문하지 않은 정점들을 queue에 넣어주며 bfs로 탐색한다
• 해당 정점의 방문 거리는 이전 정점의 방문 거리+1 이다

✏️Solution

• 양방향 인접 리스트 만들기
  (어차피 distance를 이용해 이미 방문한 정점인지 아닌지 확인 할 것이기 때문에 중복 방문할 일은 없다)

vector<vector<int>> twoEdge(50001);
    //make two-way edge
    for (int i=0; i<edge.size(); i++) {
        int n1=edge[i][0];
        int n2=edge[i][1];
        twoEdge[n1].push_back(n2);
        twoEdge[n2].push_back(n1);
    }

• queue에 1을 먼저 넣고 1에서 인접한 정점 순차 탐색

void bfs (int start) {
    queue<int> q;
    q.push(start);
    while (!q.empty()) {
        int cur=q.front();
        q.pop();
        
        for (int i=0; i<twoEdge[cur].size(); i++) {
        
        // 처음 cur==1
        //twoEdge[1] 즉, 1과 인접한 정점들 중 한 번도 방문한 적 없는 점들을 
        //queue에 넣고 해당 점까지 거리는 현재 거리 +1을 해줌
        // =>dist[newNode]=dist[cur]+1
        
        }
    }
}

🔖Source Code

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

using namespace std;
const int MAX=50001;
int maxCnt = 0;

vector<int> dist;
vector<vector<int>> twoEdge(50001);

void bfs (int start) {
    queue<int> q;
    q.push(start);
    
    while (!q.empty()) {
        int cur=q.front();
        q.pop();
        
        for (int i=0; i<twoEdge[cur].size(); i++) {
            int node=twoEdge[cur][i];
            // adj node is not visited and not 1
            if (dist[node]==0 && node!=1) {
                dist[node]=dist[cur]+1;
                q.push(node);
                if (dist[node]>maxCnt) 
                    maxCnt=dist[node];
            }
        }
    }
}

int solution(int n, vector<vector<int>> edge) {
    int answer=0;
    dist=vector<int> (n+1);
    
    //make two-way edge
    for (int i=0; i<edge.size(); i++) {
        int n1=edge[i][0];
        int n2=edge[i][1];
        twoEdge[n1].push_back(n2);
        twoEdge[n2].push_back(n1);
    }
    bfs(1);
    
    for (int i=1; i<=n; i++) 
        if (maxCnt==dist[i])
            answer++;
    
    return answer;
}