프로그래머스 (가장 먼 노드, 그래프) C++

 

그래프와 DFS의 느낌이 풍긴다면 이중 벡터를 이용해서 Adjacent List를 만들고 visited 벡터를 이용해서 BFS를 iterative하게 구성한다. 그리고 BFS의 경우 시작 노드와 얼마나 떨어져 있는지는 새로운 배열을 하나 만들어줘서 알고리즘을 작성하면 된다. while 문 안의 for 문의 경우 하나의 node를 설정해놓고 그 주변 연결된 node만을 탐색하는 것이기에 queue에서 front로 참조한 node는 변하지 않는다는 성질을 이용하여 level을 체크해주면 된다.

 

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

using namespace std;

int solution(int n, vector<vector<int>> edge) {
    int answer = 0;
    vector<vector<int>> graph(n+1);
    vector<bool> visited(n+1, false);
    vector<int> counts(n+1,0);
    queue<int> queue;
    
    // Adjacent List를 만든다. 2중 벡터를 활용
    // 방향서잉 없으므로 양쪽 둘다 넣어준다.
    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]);
    }
    
    // 1에서 가장 먼 노드를 탐색하므로 1을 먼저 넣는다.
    queue.push(1);
    visited[1] = true;
    
    // queue에 어떤 것이 들어있기만 하면 계속 반복한다.
    while(!queue.empty()) {
        
        // queue의 front의 요소를 받아온다.
        int node = queue.front();
        queue.pop();
        
        // front 요소의 주변 node를 탐색하기 위해 반복문을 구성
        for(int i = 0 ; i < graph[node].size() ; i++) {
            
            // 만약 front부터 시작하는 그래프의 연결된 노드가 방문되지 않은 경우
            if(!visited[graph[node][i]]) {
                
                // currentCount 변수를 만들어 +1 을 해준다.
                // 1에서 얼마나 떨어져있는지를 index화 시켜 비교한다.
                int currentCount = counts[node] + 1;
                visited[graph[node][i]] = true;
                
                // 방문한 node에 해당하는 index의 level을 부여한다.
                counts[graph[node][i]] = currentCount;
                
                // 해당 node를 queue에 push 해준다.
                queue.push(graph[node][i]);
            }
        }
    }
    
    // counts 배열을 begin부터 end까지 내림차순으로 sort 시킨다.
    sort(counts.begin(), counts.end(), greater<int>());
    
    // 만약 count의 가장 큰 요소와 같지 않는 경우가 나온다면 level이 낮아진 것이므로
    // 해당 조건의 경우 break 하고 그렇지 않으면 answer를 하나씩 증가시킨다.
    for(auto cnt : counts) {
        if(cnt != counts[0]) break;
        answer++;
    }
    
    return answer;
}