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

문제 설명

n개의 노드가 있는 그래프가 있습니다. 각 노드는 1부터 n까지 번호가 적혀있습니다. 1번 노드에서 가장 멀리 떨어진 노드의 갯수를 구하려고 합니다. 가장 멀리 떨어진 노드란 최단경로로 이동했을 때 간선의 개수가 가장 많은 노드들을 의미합니다.

노드의 개수 n, 간선에 대한 정보가 담긴 2차원 배열 vertex가 매개변수로 주어질 때, 1번 노드로부터 가장 멀리 떨어진 노드가 몇 개인지를 return 하도록 solution 함수를 작성해주세요.

 

제한사항

• 노드의 개수 n은 2 이상 20,000 이하입니다.
• 간선은 양방향이며 총 1개 이상 50,000개 이하의 간선이 있습니다.
• vertex 배열 각 행 [a, b]는 a번 노드와 b번 노드 사이에 간선이 있다는 의미입니다.

 

입출력 예

 

입출력 예 설명

예제의 그래프를 표현하면 아래 그림과 같고, 1번 노드에서 가장 멀리 떨어진 노드는 4,5,6번 노드입니다.

 

풀이

- graph : 정점들간의 연결 구간을 1로 나타낸 2차원 그래프

- dist : 누적 거리 합을 저장

- visit : 방문 여부

 

#include <iostream>
#include <queue>
#include <cstring>
using namespace std;

int solution(int n, vector<vector<int>> edge) {
    int answer = 0;
    
    // 그래프(dist), 방문여부(visit), 누적(dist) 초기화
    int **graph = new int*[n+1];
    int *dist = new int[n+1];
    bool *visit = new bool[n+1];
    memset(dist, 0, sizeof(int)*(n+1));
    memset(visit, false, sizeof(bool)*(n+1));
    
    for(int i = 1; i < n+1; i++) { 
        graph[i] = new int[n+1];
        memset(graph[i], 0, sizeof(int)*(n+1));
    }
    
    for(int i=0; i<edge.size(); i++){
        graph[edge[i][0]][edge[i][1]] = 1;
        graph[edge[i][1]][edge[i][0]] = 1;
    }
    
    int start_node = 1;    // 1번 정점부터 시작
    int max_distance = 0;  // 최대 거리 저장
    queue<int> q;
    q.push(start_node);    // 큐에 1번 노드를 넣고
    visit[start_node] = true;  // 1번 노드 방문 표시
    
    while(!q.empty()){
        start_node = q.front(); // 큐에서 가장 최근에 방문한 노드를 꺼내고
        q.pop();                // 큐에서 제거한다
        
        // 1~n번 정점 순회
        for(int target_node=1; target_node<=n; target_node++){
        
        	// 간선이 연결되어 있고 방문하지 않았다면
            if(graph[start_node][target_node]==1 && visit[target_node]==false){
            
            	// 가중치 1을 더해 누적해나가면서
                dist[target_node] = dist[start_node] + 1;
                
                // 가장 먼 노드의 거리를 저장한다
                if(dist[target_node] > max_distance){
                    max_distance = dist[target_node];
                }
                
                // 큐에 방문한 노드를 넣고
                q.push(target_node);
                
                // 방문표시 한다
                visit[target_node] = true;
            }
        }
    }
    
    // 최대 거리를 가지는 노드들의 개수를 구한다
    for(int i=1; i<=n; i++){
        if(dist[i] == max_distance){
            answer++;
        }
    }
    
    return answer;
}