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

문제

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

프로그래머스

접근방법

2차원 배열을 쓰려고 생각해봤는데,

시간복잡도가 안될 거 같았다.

그래서 linked list를 사용해서 풀었다.

 

노드 1을 먼저 큐에 담고,

bfs방식으로 그래프를 탐색했다.

 

탐색하면서,

visit배열에 1로부터의 거리를 저장했다.

 

코드

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

using namespace std;

class node {
public:
    int n;
    node* next;
    
    node(int n, node* next) : n(n), next(next) {}
};

int solution(int n, vector<vector<int>> edge) {
    int answer = 0;
    vector<node*> list(50001, nullptr);
    queue<int> q;
    vector<int> visit(50001, 0); 
    for (const auto& e : edge) {
        list[e[0]] = new node(e[1], list[e[0]]);
        list[e[1]] = new node(e[0], list[e[1]]);
    }
    q.push(1);
    visit[1] = 1;
    while(!q.empty()) {
        int a = q.front();
        q.pop();
        
        node* nd = list[a];
        while(nd) {
            if (!visit[nd->n]) {
                q.push(nd->n);
                visit[nd->n] = visit[a] + 1;
            }
            nd = nd->next;
        }
    }
    
    int cnt = 0;
    cnt = *max_element(visit.begin(), visit.end());
    for (int i = 0;i<visit.size();i++) {
        if (cnt == visit[i]) {
            answer++;
        }
    }
    
    
    return answer;
}

개선할 점

...