프로그래머스 - 가장 먼 노드

가장 먼 노드

이 문제는 그래프 문제이다.
사실 그래프에 대한 문제는 어느정도 정형화된 유형이 있기는 하다.
보통 문제의 조건들과 더불어 그래프의 유형 (인접행렬 혹은 인접리스트)가 주어진다.

그 후 적절한 알고리즘을 찾아서 적용하면 된다. (말이 쉽지)

내가 생각하기에 대충 유형과 알고리즘을 분류해보자면

1. 몇 가지인지 전체 경우를 찾는 문제 (보통 dfs..백트래킹..)

2. 최단거리 관련 (보통 bfs 혹은 다익스트라..)

3. 연결성 관련 (union-find, cruskal..)

정도로 생각할 수 있는 것 같다.

이 문제는

1. 연결리스트를 사용했으며
2. 최단거리를 요구한다.

이므로 이에 맞게 풀면 된다.

참고로 이 문제에서는
bfs도 다익스트라도 가능한 문제이지만
딱히 길이에 따른 가중치가 주어져있지는 않다.
이 때는 bfs를 써도 무방하다.

하지만 다른 최단거리를 묻는 문제의 대부분은
다익스트라를 요구할것이니 모른다면 공부를 하자.

참고로 최단거리를 구할 때 간선 중 음수 가중치를 가지는
간선이 있다면 다익스트라를 쓰면 안된다.
그때는 Belman-Ford 알고리즘을 이용하자.

계속 옆길로 열심히 샜다. 코드는 다음과 같다.

#include <string>
#include <vector>
#include <queue>
using namespace std;
queue<int> q;
bool visited[20001]={0};
int dist[20001]={0};
vector<int> adj[20001];
int bfs(int x);
int solution(int n, vector<vector<int>> edge) {
    int answer = 0;
    for(int i=0;i<edge.size();i++){
        int x = edge[i][0];
        int y = edge[i][1];
        adj[x].push_back(y);
        adj[y].push_back(x);
    }
    int res = bfs(1);
    for(int i=0;i<=n;i++){
        if(dist[i]==res) answer++;
    }
    return answer;
}
int bfs(int x){
    int res = 0;
    dist[x]=0;
    visited[x]=true;
    q.push(x);
    while(!q.empty()){
        int a = q.front();
        q.pop();
        for(auto s:adj[a]){
            if(visited[s]) continue;
            visited[s]=true;
            dist[s]=dist[a]+1;
            res=max(res,dist[s]);
            q.push(s);
        }
    }
    return res;
}