프로그래머스 가장 먼 노드 [C++, 최장거리,BFS)

 

문제

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

프로그래머스

 

 

해설

이 문제를 처음 보고선, 단순하게 시작점부터 각 노드간의 최단 거리를 모두 찾고, 그 중 가장 긴 거리의 수를 고르려고 했다. 이 방법엔 2가지 솔루션이 있다.

 

1)  시작점에서 각 노드간의 거리를 다익스트라로 구하기:  [ V*O(V^2) == O(V^3) ]

2) 플로이드 와샬로 각 정점들간의 최단 거리 모두 구한 뒤, 시작점에서 각노드간 최단거리만 사용하기 [O(V^3)]

 

하지만, 주어진 노드의 제약조건은 최대 2만개까지 허용한다. 따라서 3제곱 풀이로 들어가는 것은 물론이고, 2제곱 풀이도 1억 이상의 연산으로 시간초과가 발생한다.

 

여기서 내가 잘못된 접근을 하고 있다는 것을 인지할 수 있었다.

 

그리고 "각 정점간의 거리는 모두 같다(단위 길이)" 라는 것을 보고, bfs를 통한 최단 거리 풀이가 생각났다.

 

https://codenme.tistory.com/6

최단거리류 알고리즘에 대해서(다익스트라,벨만포드,플로이드 등등)

위의 글은 최단거리류 알고리즘에 대해 정리한 글이니 참고하자.

 

아무튼, bfs가 FIFO 구조인 큐를 사용하고, 단위길이라는 특성을 혼합하면, 결국 qu에서 길이가 짧은순으로 pop되게 된다.

쉽게 말하자면,bfs 탐색에 사용할 queue에 {시작점에서의 거리, 정점} 을 넣게되면, 아래와 같이 데이터를 넣게 될 것이다.

 

               [ {1,x},{1,x},{2,x},{2,x},{2,x},{2,x},{2,x},{3,x},{3,x},{3,x},{3,x},{3,x},.....]

 

우리가 찾아야하는것은 "최장 거리의 개수" 이다.

qu에서 값을 꺼내올 때, 만약 dist가 변경되면(더 큰 값으로 갱신되면) count하고, 해당 dist의 개수를 cnt라는 갯수를 저장하는 변수에 누적해나가면 끝이다.

 

코드

#include <string>
#include <vector>
#include<queue>
using namespace std;
int visit[20010];
vector<int> e[20010];



int solution(int n, vector<vector<int>> edge) {
    //플로이드 와샬 이후 가장 높은 값 찾고, 그 개수 찾기. 
    int answer = 0;
    for(int i=0;i<edge.size();i++){
        e[edge[i][0]].push_back(edge[i][1]);
        e[edge[i][1]].push_back(edge[i][0]);
    }
    queue<pair<int,int>> qu;
    for(int i=0;i<e[1].size();i++){
        qu.push({1,e[1][i]});
    }
    int prev_dist=0,cnt=0;
    int a=50;
    visit[1]=1;
    while(!qu.empty()){
        int dist= qu.front().first, v=qu.front().second;
        qu.pop();
        if(visit[v]) continue;
        visit[v]=1;
       // printf("now: %d, dist: %d \n",v,dist);
        if(prev_dist<dist){
            cnt=0; 
            prev_dist=dist;
        }
        cnt++;//해당 길이의 정점 개수 추가   
        for(int i=0;i<e[v].size();i++){    
            qu.push({dist+1,e[v][i]});
        }
    }
    answer=cnt;
    return answer;
}