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

프로그래머스의 Lv.3 가장 먼 노드입니다.

문제 출처

가장 먼 노드

문제 해설

문제를 보면, 바로 BFS 문제인 것을 확신할 수 있다.
다만, 필자도 항상 그렇지만, BFS를 사용해야할지, DFS를 사용해야할지 헷갈릴 때가 많이 있다.
이번을 기회로 삼아 정리를 해보자.

1. BFS
   1. BFS는 Queue로 구현한다.
      
   2. BFS는 시작 노드에서부터 거리를 구할 수 있다.
      
2. DFS
   1. DFS는 Stack으로 구현한다.
      
   2. DFS는 시작 노드에서부터 거리를 구할 수 없다.
      
      

위의 BFS와 DFS의 차이점을 고민해 봤을 때, 이 문제는 1번 노드부터 시작해서, 각 노드까지의 거리를 구해야 한다.
거리를 구하는 로직은 BFS임으로 이 문제를 BFS로 풀어보자.

#include <bits/stdc++.h>

using namespace std;

int check[20001];
int arrCount[20001];

int solution(int n, vector<vector<int>> edge) {
    int answer = 0;
    
    vector<vector<int>> v(n+1);
    queue<int> q;
    
    for(int i=0;i<edge.size();++i){
        int start = edge[i][0];
        int end = edge[i][1];
        v[start].push_back(end);
        v[end].push_back(start);
    }
    
    int maxNum = 0;
    q.push(1);
    arrCount[1] = 0;
    check[1] = true;
    while(q.empty() == false){
        int cur = q.front(); q.pop();
        
        for(auto nxt : v[cur]){
            if(check[nxt] == true) continue;
            q.push(nxt);
            check[nxt] = true;
            arrCount[nxt] = arrCount[cur] + 1;
            if(maxNum < arrCount[nxt]) maxNum = arrCount[nxt];
        }
    }
    
    for(int i=1;i<n+1;++i)
        if(arrCount[i] == maxNum) ++answer;    
    
    return answer;
}