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

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

프로그래머스

 

프로그래머스 코딩 테스트 고득점 Kit에 포함된 Level 3 그래프 문제입니다.

 

#include <string>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

queue<int> q;
int depth[20001];
vector<int> AL[20001];

void init(vector<vector<int>>& edge){
    for(vector<int> v : edge){
        AL[v[0]].push_back(v[1]);
        AL[v[1]].push_back(v[0]);
    }   
}

int solution(int n, vector<vector<int>> edge) {
    int answer = 0;
    init(edge);
    q.push(1);
    depth[1] = 1;
    while(!q.empty()){
        int curr = q.front();
        q.pop();
        for(int nxt : AL[curr]){
            if(!depth[nxt]){
                q.push(nxt);
                depth[nxt] = depth[curr] + 1;
            }        
        }
    }
    
    int mx = *max_element(depth+1, depth+n+1);
    
    for(int i = 1; i <= n; ++i){
        if(depth[i] == mx) ++answer;
    }
    
    return answer;
}

 

문제가 어렵다기보다는 주어진 edge의 구조가 평소 BOJ 등에서 그래프 문제를 풀 때 쓰던 구조가 아니었기 때문에 따로 init()을 통해 익숙한 형태로 모델링하는 작업이 필요했습니다. 양방향 그래프인 것에도 주의해야 합니다.

 

그 외에는 BFS를 통해 1번 node를 root로 했을 때 각 node들의 depth를 체크해 주고 가장 깊은 depth를 갖는 node들의 개수를 체크하여 반환하면 되는 비교적 간단한 문제입니다.