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번 노드 사이에 간선이 있다는 의미입니다.

입출력 예

Solution

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

vector<int> Vec[50001];
int node[20001];
int maxLength;

void BFS(){
    queue<int> q;
    q.push(1);
    while(!q.empty()){
        int current = q.front();
        q.pop();
        for(int i = 0; i < Vec[current].size(); i++){
            if(node[Vec[current][i]] == 0 && Vec[current][i] != 1){
                node[Vec[current][i]] = node[current] + 1;
                q.push(Vec[current][i]);
                maxLength = max(maxLength, node[Vec[current][i]]);
            }
        }
    }
}

int solution(int n, vector<vector<int>> edge){
    int answer = 0;
    for(int i = 0; i < edge.size(); i++){
        Vec[edge[i][0]].push_back(edge[i][1]);
        Vec[edge[i][1]].push_back(edge[i][0]);
    }
    BFS();
    for(int i = 1; i <= n; i++){
        if(maxLength == node[i]) answer++;
    }
    return answer;
}

입출력 예시의 데이터는 이런 상황이라 생각하면 된다. 다시 말하자면, 가장 멀리 떨어진 노드란 최단경로로 이동했을 때 간선이 가장 많은 놈이라 할 수 있다.
양방향 그래프라는 정보를 통해 인접행렬 처리를 할 때 좀더 편하게 할 수 있다. 사실 뭐 크게 어렵진 않다. 출발 시점도 이미 정해졌고 각 노드별로 최단거리로 도착했을 때 이동거리를 저장해둔다면 해결 될 문제라 생각한다.

BFS가 뭔지 잘 모르겠는 사람을 위해 https://velog.io/@sierra9707/Algorithm-DFS-BFS
이미 여기까지 풀이를 해놓고 이제와서 BFS가 뭔가 라는 질문을 해 봐야 의미는 없다만...내가 쓴 글좀 봐달란 소리다. 저 양반이 글 쓰다 어지간히 심심했는가보다 하고 넘겨주시길 바란다.

vector<int> Vec[50001];
int node[20001];
int maxLength;

void BFS(){
    queue<int> q;
    q.push(1);
    while(!q.empty()){
        int current = q.front();
        q.pop();
        for(int i = 0; i < Vec[current].size(); i++){
            if(node[Vec[current][i]] == 0 && Vec[current][i] != 1){
                node[Vec[current][i]] = node[current] + 1;
                q.push(Vec[current][i]);
                maxLength = max(maxLength, node[Vec[current][i]]);
            }
        }
    }
}

간단하다. BFS를 통해 1번 노드부터 탐색을 시작하고 노드에 방문하는대로 해당 노드를 방문하는 데 거친 간선들을 갱신해준다.
전역변수 처리를 해 주었으니 초기에는 모든 노드들의 이동거리 값이 0으로 초기화 되어있을 것이다. 그렇지만 탐색을 할 수록 기존의 값에 +1 씩 추가하며 갱신하게 될 것이다. 또한 매 탐색마다 maxLength를 구하는데, 자연스럽게 가장 멀리 떨어진 노드의 값이 갱신될것이다.

int solution(int n, vector<vector<int>> edge){
    int answer = 0;
    for(int i = 0; i < edge.size(); i++){
        Vec[edge[i][0]].push_back(edge[i][1]);
        Vec[edge[i][1]].push_back(edge[i][0]);
    }
    BFS();
    for(int i = 1; i <= n; i++){
        if(maxLength == node[i]) answer++;
    }
    return answer;
}

그리고 값들을 뒤져보면서 maxLength의 값을 가진 노드들을 찾아주면 끝이다.

BFS만 할 줄알면 풀 수 있다. DFS는 최단거리를 구해야하는 입장이라 함부로 쓸 수는 없을 것이다. 또한 값이 이상하게 나올수도 있으니까.