프로그래머스 - 49189 가장 먼 노드

문제

https://school.programmers.co.kr/learn/courses/30/lessons/49189

프로그래머스

1번 노드에서 가장 멀리 떨어진 노드의 개수를 구하는 문제였다.

 

문제 풀이

n이 최대 20000이어서 플루이드 워셜 알고리즘을 사용하면 시간 초과가 날 것 같아서 BFS로 각 노드까지의 거리를 구했다.

 

BFS는 레벨 별로 탐색하기 때문에 탐색할 때마다 dist 배열을 갱신했다. 그리고 탐색할 때마다 최대 dist를 계속 갱신해줬다. 마지막에 최대 dist와 dist가 같은 노드들의 개수를 세면 답이 된다.

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

using namespace std;

vector<int> G[20001];
int dist[20001]; //1번 노드와의 거리
int maxDist = 0;

void findDist(int start){
    queue<pair<int,int>> q; //node, dist
    
    q.push({start,0});
    
    while(!q.empty()){
        int nowNode = q.front().first;
        int nowDist = q.front().second;
        q.pop();
        //printf("nowNode: %d nowDist: %d\n",nowNode, nowDist);
        maxDist = max(maxDist, nowDist);
        
        for(int i=0;i<G[nowNode].size();i++){
        int nextNode = G[nowNode][i];
        
            if(dist[nextNode] == 0 && nextNode != 1){ //방문 전
                dist[nextNode] = nowDist+1;
                q.push({nextNode, nowDist+1});
            }
        }
    }
  
}

int solution(int n, vector<vector<int>> edge) {
    int answer = 0;
    
    //그래프 만들기
    for(vector<int> e:edge){
        int a = e[0];
        int b = e[1];
        
        G[a].push_back(b);
        G[b].push_back(a);
    }
    
    findDist(1);
      
    /*
    for(int i=1;i<=n;i++){
        printf("%d ",dist[i]);
    }
    printf("\n");
    */
    
    for(int i=1;i<=n;i++){
        if(dist[i] == maxDist){
            answer++;
        }
    }
    
    return answer;
}