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

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

코딩테스트 연습 - 가장 먼 노드

문제 설명

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

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

제한사항

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

입출력 예

n	vertex	return
6	[[3, 6], [4, 3], [3, 2], [1, 3], [1, 2], [2, 4], [5, 2]]	3

 

입출력 예 설명

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

풀이

1) 그래프를 vector형을 가지는 배열로 이용하여 표현 하였다.
각 노드 양방향으로 이어져 있으며 vertex의 시작점과 끝점을 파싱하여 각각의 노드들을 연결해주었다.

vector<int> arrayNum[20002]; // 그래프 배열 선언.

for(int i=0; i < edge.size(); i++) {
        
        int sp = edge[i][0]; // 시작점
        int ap = edge[i][1]; // 도착점
        
        arrayNum[sp].push_back(ap);
        arrayNum[ap].push_back(sp);
}

  

2) 그리고 모든 노드를 탐색하는 것도 있지만 가까운 순서대로 방문하는 BFS 알고리즘을 사용하였다.
보통 BFS 알고리즘에서 단순히 방문 포인트만을 Queue에 Push하게 되는데 해당 문제에서는 1번 노드로 부터의 길이    를 파악해야 하므로 pair를 통해 distance값 또한 Queue에 Push 하였다.

queue<pair<int,int>> que;

int Num = que.front().first;
int Numcount = que.front().second;

que.push(make_pair(temp,Numcount+1));

 

3) 가장 멀리 떨어져 있는 노드값을 판단해야 하므로 거리에 따른 배열을 따로 선언하여 노드들을 관리하였다.

vector<int> arraydistance[20002]; // 거리 별 vector<int>
arraydistance[Numcount].push_back(Num); //Numcount : 1번 노드부터의 거리, Num: 노드 숫자.

 

최종 풀이 코드

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

vector<int> arrayNum[20002]; // 그래프 그리기
vector<int> arraydistance[20002]; // 거리 별 vector<int>
queue<pair<int,int>> que; //pair first : 노드 숫자, second : 1번 노드부터의 거리
bool visited[20002] ={false,};

int maxdistance = 0;

int max(int a, int b){
    return a>b ? a:b;
}


void bfs(int sp) {
    
    que.push(make_pair(sp,0));
    visited[sp] = true;
    
    while(!que.empty()) {
        
        int Num = que.front().first;
        int Numcount = que.front().second;
  
        que.pop();
     
        arraydistance[Numcount].push_back(Num);
        maxdistance = max(maxdistance, Numcount); //가장 먼 거리 체크
        
        for(int i=0; i<arrayNum[Num].size(); i++) {
            
            int temp = arrayNum[Num][i];
            
            if(visited[temp] == false) {
                que.push(make_pair(temp,Numcount+1));
                visited[temp] = true;
            }
           
        }    
    }
}

int solution(int n, vector<vector<int>> edge) {
    
    sort(edge.begin(), edge.end());
    
    for(int i=0; i<edge.size();i++) {
        
        int sp = edge[i][0];
        int ap = edge[i][1];
        
        arrayNum[sp].push_back(ap);
        arrayNum[ap].push_back(sp);
    }
    
 
    bfs(1);
        
    int answer = arraydistance[maxdistance].size();
    return answer;
}