(C++) - 프로그래머스(고득점 kit - 그래프) : 가장 먼 노드

programmers.co.kr/learn/courses/30/lessons/49189

코딩테스트 연습 - 가장 먼 노드

bfs문제였습니다.

 

풀이방법

 1. 주어진 간선들이 단방향으로 주어지기 때문에 양방향 인접 그래프로 변환해줍니다.

 2. 1번 노드에서 시작하여 bfs를 시행합니다. 연결된 노드들까지의 최소거리를 dist배열에 저장합니다.

 2. 가장 먼 노드까지의 거리를 저장합니다.

 3. 해당거리와 같은 거리의 노드들의 개수를 세줍니다.

 

Code

#include <bits/stdc++.h>
#define MAX 0x3f3f3f3f
using namespace std;

int bfs(vector<int> graph[],vector <int> &dist, int n){
    queue <int> q;
    int visited[20001], maxDist = 0,cnt = 0;;
    memset(visited,0,sizeof(visited));
    q.push(1);
    visited[1] = 1;
    while(!q.empty()){
        int x = q.front();
        q.pop();
        for(int i = 0; i < graph[x].size(); i++){
            int nx = graph[x][i];
            if(visited[nx]) continue;
            visited[nx] = 1;
            dist[nx] = dist[x] + 1;
            maxDist = max(maxDist, dist[nx]);
            q.push(nx);
        }
    }
    for(int i = 1; i<= n; i++){
        if(dist[i] == maxDist) cnt++;
    }
    return cnt;
}

int solution(int n, vector<vector<int>> edge) {
    int answer = 0;
    vector <int> dist(edge.size(),0);
    vector <int> graph[n+1];
    sort(edge.begin(),edge.end());
    for(int i = 0; i < edge.size(); i++){
        graph[edge[i][0]].push_back(edge[i][1]);
        graph[edge[i][1]].push_back(edge[i][0]);
    }  
    return bfs(graph,dist,n);
}