[프로그래머스] 가장 먼 노드

---

🔗 문제 링크

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

프로그래머스

---

반응형

728x90

👩‍💻 코드

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

using namespace std;

int solution(int n, vector<vector<int>> edge) {
    int answer = 0;
    int max = 0;
    vector<vector<int>> graph(n, vector<int>(n, 0));
    vector<bool> visited(n, false);
    queue<pair<int, int>> q;
    
    for(auto e : edge){
        graph[e[0]-1][e[1]-1] = 1;
        graph[e[1]-1][e[0]-1] = 1;
    }
    
    q.push({0,0});
    visited[0] = true;
    
    while(!q.empty()){
        auto v = q.front();
        int node = v.first;
        int count = v.second;
        
        if(count > max){
            answer = 1;
            max = count;
        }else if(count == max){
            answer++;
        }
        
        q.pop();
        
        for(int i=0; i<n; i++){
            if(graph[node][i] == 1 && !visited[i]){
                q.push({i, count+1});
                visited[i] = true;
            }
        }
    }
    
    return answer;
}

---

📝 풀이

우선 주어진 간선의 정보로 인접 리스트를 초기화합니다.

1번 노드에서 가장 멀리 떨어진 노드가 몇 개인지 구하는 것이니 BFS 탐색을 해야합니다.

1번 노드를 기준으로 탐색을 시작하여 이전 노드와 이어져있고 아직 방문하지 않은 노드를 순서대로 방문합니다.

방문할 때마다 count를 증가시켜 1번 노드와 얼마나 떨어져있는지 체크합니다.

노드에 방문할 때 count값이 max보다 크면 max값을 새로 갱신 후 asnwer을 1로 변경합니다.

만약 max값과 같다면 asnwer을 증가시킵니다.

최종적으로 탐색이 끝나면 answer을 return 합니다.