프로그래머스 가장 먼 노드 문제

안녕하세요! 오늘도 프로그래머스 문제    가장 먼 노드를 풀어보았습니다.

 

사실 이 문제는   가중치가 없는 그래프에 최단거리 이야기까지 나왔으니  100% bfs를 이용하면 쉽게 풀 수 있습니다.

bfs의 특징을 이용하면  한단계 한단계씩 다음 노드로 접근하게될거고, 

마지막 접근한 노드들만 쭉 찾아서 갯수세주면  바로 해결!

 

조금 특이한건  bfs탐색을 위한  발견여부 배열에   해당 점을 발견한 당시  거리값을 저장시켰다는 점입니다.

마지막에   거리 최대값을 가진  애들만 쭉 반복문돌리며  갯수 세는식으로 만들기위해 ㅎㅎ. 

 

그럼 오늘도 파이팅입니다!

 

 

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

using namespace std;

int solution(int n, vector<vector<int>> edge) {
    
    //간선이용해 그래프 표현
    vector<int> graph[20001]; 
    
    for(int i=0;i<edge.size();i++){
        graph[edge[i][0]].push_back(edge[i][1]);
        graph[edge[i][1]].push_back(edge[i][0]);
    }
    
    int answer = 0;
    queue<pair<int, int>> que;
    int discover[20001]={};
    
    que.push({1,0});
    discover[1]=1; //bfs를 위한 발견여부 저장
    int max = 1;
    while(!que.empty()){
        pair<int, int> ft = que.front();
        que.pop();
        
        for(int i=0;i<graph[ft.first].size();i++){
            //연결되있는데 발견한적없었다면
            if(discover[graph[ft.first][i]] == 0){
                discover[graph[ft.first][i]] = ft.second+1; //발견처리하고
                que.push({graph[ft.first][i], ft.second+1}); //탐색위해 큐에 푸시
                
                if(max < ft.second+1) max = ft.second+1;
            }
        }
        
    }
    
    for(int i=1;i<=n;i++){
        if(discover[i] == max) answer++;
    }
    
    return answer;
}

 

 

 

<박기완의 c언어 코딩교육 시리즈 >

게임개발을 희망하는 초등학생, 중학생, 고등학생들을 위한 c언어 책

 

초등, 중등, 고등  1:1 원격 c언어 교육문의

010 - 4537 - 7998

 

현재 대치동 학원에서 코딩강사로 활동중에 있습니다

영재고, 과학고 내신 /

초등, 중등, 고등 입문반, 초급, 중급, 정올반 /

앱, 게임 제작반  문의주세요!