[프로그래머스] 가장 먼 노드 (C++)

1. 문제

https://programmers.co.kr/learn/courses/30/lessons/49189/solution_groups?language=cpp 

프로그래머스

2. 풀이

BFS를 활용한 그래프 문제.

1) 양방향 그래프이므로 그래프의 연결 상태를 저장하낟.

2) 1번 노드부터 시작하여 방문 여부를 체크한다.

3) 방문하지 않은 노드의 경우 dist 거리를 갱신하고 방문 여부를 체크, 큐에 저장

4) 2~3번 반복

5) dist에 저장한 거리 중 가장 최대 값을 구한다.

6) 최대값 max_val인 노드가 몇 개인지 answer 갱신

 

3. 코드

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

using namespace std;

int solution(int n, vector<vector<int>> edge) {
    int answer = 0;
    vector<vector<int>> graph(n+1, vector<int>());
    vector<int> dist(n+1, 0);
    vector<bool> visit(n+1, false);
    queue<int> q;
    
    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]);
    }
    
    q.push(1); //1에서부터 시작
    dist[1] = 0;
    visit[1] = true;
    while(!q.empty()){
        int cur = q.front();
        q.pop();
        
        for(int i=0; i<graph[cur].size(); i++){
            int v = graph[cur][i];
            if(!visit[v]){
                dist[v] = dist[cur]+1;
                visit[v] = true;
                q.push(v);
            }
        }

    }
    int max_val =0;
    for(int i=1; i<=n; i++){
        if(max_val < dist[i]){
            max_val = dist[i];
        }
    }
    
    for(int i=1; i<=n; i++){
        if(max_val == dist[i]){
            answer++;
        }
    }
    
    return answer;
}