[graph + bfs] 프로그래머스 -가장 먼 노드 c++

문제 링크:https://programmers.co.kr/learn/courses/30/lessons/49189

 

참고한 정답 출처: https://0xd00d00.github.io/2021/07/10/programmers_distance.html

[프로그래머스][C++][고득점 Kit] 가장 먼 노드 - doodoo's coding

 

 

간단 회고:

	O	X
내가 직접 풀었나?		✔
다른 사람 풀이를 참고 하였나?	✔
어려웠나?	✔
푸는데 오래걸렸나?		✔

✅✔

 

c++로 처음 bfs관련된 문제를 시도했다.

 

당연히 처음 주어진 배열을 통해 2차원 그래프를 만드는 것부터 막혔기에 빠르게 정답을 보고 유형을 익혔다.

 

 

참고한 타 풀이 + 내 이해를 담은 주석

 

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

using namespace std;

//출처 : https://0xd00d00.github.io/2021/07/10/programmers_distance.html

int solution(int n, vector<vector<int>> edge) {
    //2차원 그래프를 만들기 위한 2차원 배열
    vector<vector<int>> graph(n+1); 
    
    //counter를 위한 배열, 노드 번호(index), 깊이(value)
    vector<int> counts(n+1, 0); //0으로 초기화
    
    //visited 배열
    vector<bool> visited(n+1, false);
    
    //BFS를 위한 큐
    queue<int> queue;
    
    int answer = 0;
    
    // 인접 양방향 리스트 기반 그래프 생성
    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]);
    }
    
    queue.push(1); // 시작점
    visited[1] = true;
    
    //BFS
    while(!(queue).empty()) {
        int node = queue.front();
        queue.pop();
        
        // 큐에서 꺼낸 노드에 연결된 모든 노드들을 for문 돌기
        for (int i = 0; i < graph[node].size(); i++) {
            
            int nodeLinkedToNode = graph[node][i];
            //방문 검사
            if (!visited[nodeLinkedToNode]) {
                // 최대거리를 알아야하기에 거리 증가, 너비 우선 탐색이기에 높이가 보장
                int currentCount = counts[node] + 1; //상위노드 깊이 + 1
                
                //방문 확인;
                visited[nodeLinkedToNode] = true;
                
                //방문 후 카운트(깊이) 기록;
                counts[nodeLinkedToNode] = currentCount;
                
                //현재 노드에서 연결된 노드에 연결된 점들을 확인 할 수 있게 큐에 push
                queue.push(nodeLinkedToNode);
            }
        }
    }
    
    //깊이가 깊은 순으로 정렬;
    sort(counts.begin(), counts.end(), greater<int>());
    for (auto cnt : counts) {
        //가장 깊은 count[0]의 깊이보다 얕다면 탈출;
        if (counts[0] != cnt) break;
        
        //답 개수 기록
        answer++;
    }
    
    return answer;
}