[그래프] 가장 먼 노드

프로그래머스

 

인접 노드로 그래프를 구하고 BFS로 최단 거리의 노드의 개수를 구하는 문제다.

자칫하다가 DFS풀 여지도 있는데 DFS로 풀게 되면 최대한 깊이 우선 도달하기 때문에 최단 경로가 나오지 않는다.

BFS를 진행하면서 이전 경로의 값을 더해주면서 해당 노드까지 걸리는 거리를 구하고, 다 구했다면 MAX값을 구해 RETURN을 해주면 된다.

 

이때 주의할 점은 VECTOR를 인자로 넘겨줄 때 주소값을 넘겨줘야한다는 것이다. 아무 생각 없이 벡터 그대로 넘겨줬다가 계속 답이 틀리길래 ㅠㅠ 거의 한 시간은 헤맨 것 같다!!

 

#include <string>
#include <vector>
#include <iostream>
#include <queue>
using namespace std;

void bfs(int x, vector<vector<int>>& graph, int* maxLength, vector<bool>& visited){
    queue<int> q;
    q.push(x);
    visited[x] = true;
    
    while(!q.empty()){
        int n = q.front();
        q.pop();
        
        for(int i = 0; i < graph[n].size(); i++){
            int next = graph[n][i];

            if(!visited[next]){
                visited[next] = true;
                maxLength[next] += maxLength[n];
                
                cout << maxLength[next] << ", " << maxLength[n] << endl;
                q.push(next);
            }
        }
    }
    
}

int solution(int n, vector<vector<int>> edge) {
    int answer = 0;
    
    vector<vector<int>> graph(n + 1);
    int* maxLength = new int[n + 1];
    vector<bool>visited(n + 1);
    
    for (int i = 1; i <= n; i++) {
        maxLength[i] = 1; 
        visited[i] = false; 
    }   
    
    for(vector<int> e : edge){
        graph[e[0]].push_back(e[1]);
        graph[e[1]].push_back(e[0]);
    }
    
    bfs(1, graph, maxLength, visited);
    
    int cnt = 0;
    int max = 0;
    
    for(int i = 1; i <= n; i++){
        
        if(answer < maxLength[i]){
            answer = maxLength[i];
            cnt = 1;
        } else if(answer == maxLength[i]) cnt++;
    }
    
    return cnt;
}