[프로그래머스/c++/Lv3] 가장 먼 노드

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

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

 

문제 요약

 

n개의 노드가 있는 그래프, 각 노드는 1부터 n까지 번호가 적혀있다.

1번 노드에서 가장 멀리 떨어진 노드의 개수를 구하려고 한다.

→ 가장 멀리 떨어진 노드란, 최단 경로로 이동했을 때 간선의 개수가 가장 많은 노드를 의미한다.

노드의 개수 n, 간선에 대한 정보가 담긴 2차원 배열 vertex 가 주어진다.

1번 노드로부터 가장 멀리 떨어진 노드가 몇 개인지 return 하라.

 

제한 사항

•  2 ≤ n ≤ 200,000
• 간선은 양방향 (1 ≤ E ≤ 50,000)
• vertex 배열 각 행 [a, b]는 a번 노드와 b번 노드 사이에 간선이 있다는 의미

 

 

 

---

 

 

 

간선의 정보를 담은 2차원 벡터 edge를 입력받아서 vector <int> graph [] 2차원 벡터에 넣어서 그래프를 만들었는데 이때 문제에서의 그래프는 양방향이므로 {1, 3}이라면 1, 3에 관한 간선의 정보를 넣어줬다.

그 후, 1부터 정점 i까지의 거리를 저장하는 dist[]배열을 -1로 초기화해줬다. 이 배열은 이 정점을 지났는지 체크할 수 있는 요소가 될 수 있도록 -1로 초기화를 해줬다. 

그래프 탐색은 BFS, DFS가 있는데 최단 거리를 구하고 싶으면 BFS가 좀 더 적합하기 때문에 BFS로 구현했다. 

(DFS는 깊이 우선 탐색으로 최단 거리보다는 하나의 브런치를 깊게 파고 들어가서, 나온 결과가 최단 거리가 아닐 수 있기 때문에 BFS 너비 우선 탐색이 더 적합하다)

 

가장 먼저 시작점인 1부터 큐에 넣고 1의 인접 노드로 이동하면서 방문한 곳인지 확인하고 방문한 곳이 아니라면 +1을 해준다. 이 문제는 간선의 개수를 세는 것이기 때문에 +1로 해준다. 그 후, 해당 노드를 큐에 넣어주고 다음 인접 노드로 진행한다.

큐가 비게 되면 모든 노드를 방문한 것으로 BFS 함수를 종료한다.

 

이로써 1부터 모든 노드로의 거리를 dist 배열에 저장했고 dist를 돌면서 가장 큰 값을 저장하고 해당 값과 같은 값의 dist배열 원소가 있다면 카운팅을 해주고 출력한다.

 

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

int dist[num];

void bfs(int s, vector<int> g[]){
    queue<int> q;
    q.push(s);
    dist[s] = 0;
    while(!q.empty()){
        int x = q.front(); q.pop();
        for(int i=0; i<g[x].size(); i++){
            int y = g[x][i];
            if(dist[y] != -1) continue; //방문한 곳이라면 패스
            dist[y] = dist[x] + 1;
            q.push(y);
        }
    }
}

int solution(int n, vector<vector<int>> edge) {
    vector<int> graph[n+1];
    int answer = 0;
    int Max = 0;
    for(int i = 0; i<edge.size(); i++){
        graph[edge[i][0]].push_back(edge[i][1]); //양방향이므로 둘다 저장
        graph[edge[i][1]].push_back(edge[i][0]);
    }
    for(int i=1; i<=n; i++) dist[i] = -1; //거리 초기화
    bfs(1, graph);
    for(int i=1; i<=n; i++) Max = Max < dist[i] ? dist[i] : Max; //가장 멀리 떨어진 거리 max 구하기
    for(int i=1; i<=n; i++) if(Max == dist[i]) answer++; //가장 멀리 떨어진 노드 카운팅
    return answer;
}

 

 

 

 

 

 

💡공부 및 기록용 블로그이므로 오류가 있을 수 있습니다.💡

만약 문제에 오류나 오타가 있다면 댓글로 알려주세요➿
언제나 환영합니다. 감사합니다. 화이팅!