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

가장 먼 노드

---

1. 이해하기

• 1번 노드에서 가장 먼 노드의 갯수를 구한다. 가장 멀리 떨어진 노드란 최단 경로로 이동했을 때 간선의 개수가 가장 많은 노드들을 의미한다.
• bfs를 이용해서 구할 수 있다.

---

2. 구현하기

• bfs를 이용하여 1번에서 각 노드까지의 거리를 구한다.

  • 그 이전에 edge로 주어진 각 노드들의 연결관계를 인접리스트로 바꾼다.

  void bfs() {
      queue<int> q;
      q.push(1);
      visited[1] = true;
      dist[1] = 0;
      while(!q.empty()) {
          int here = q.front();
          q.pop();
          for(int i = 0; i < adj[here].size(); i++) {
              int there = adj[here][i];
              if(visited[there]) continue;
              q.push(there);
              dist[there] = dist[here]+1;
              visited[there] = true;
          }
      }
  }

• 거리 중에서 가장 큰 거리 값을 찾고 이 값과 같은 거리의 개수가 몇개 있는지를 찾는다.

  int solution(int n, vector<vector<int>> edge) {
      int answer = 0;
      for(int i = 0; i < edge.size(); i++) {
          int u = edge[i][0], v = edge[i][1];
          adj[u].push_back(v);
          adj[v].push_back(u);
      }
      int maxDist = 0;
      bfs();
      for(int i = 1; i <= n; i++) {
          maxDist = max(maxDist,dist[i]);
      }
      for(int i = 1; i <= n; i++) {
          if(maxDist == dist[i]) answer++;
      }
  
      return answer;
  }

---

3. 전체 코드

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

vector<int> adj[20001];
int dist[20001];
bool visited[20001];

void bfs() {
    queue<int> q;
    q.push(1);
    visited[1] = true;
    dist[1] = 0;
    while(!q.empty()) {
        int here = q.front();
        q.pop();
        for(int i = 0; i < adj[here].size(); i++) {
            int there = adj[here][i];
            if(visited[there]) continue;
            q.push(there);
            dist[there] = dist[here]+1;
            visited[there] = true;
        }
    }
}

int solution(int n, vector<vector<int>> edge) {
    int answer = 0;
    for(int i = 0; i < edge.size(); i++) {
        int u = edge[i][0], v = edge[i][1];
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    int maxDist = 0;
    bfs();
    for(int i = 1; i <= n; i++) {
        maxDist = max(maxDist,dist[i]);
    }
    for(int i = 1; i <= n; i++) {
        if(maxDist == dist[i]) answer++;
    }

    return answer;
}