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

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

코딩테스트 연습 - 가장 먼 노드 | 프로그래머스

해당 문제는 그래프 내에서 정점 1로부터 가장 멀리 있는 노드들의 개수를 구하는 문제였다.

나는 BFS를 통해 탐색하면서 가장 멀리 있는 노드들의 수를 계산하는 방식으로 처리하였다.

 

이 때, edge들이 양방향이라는 문제 조건에 맞춰 반대 방향의 edge들도 추가해주었다. 그리고 pair<int,int>를 활용해 현재 방문중인 index와 1로부터의 거리를 함께 queue에 저장하여 처리하여서 손쉽게 해결할 수 있었다.

(해당 문제는 효율성 검사를 하지 않아서 지저분한 코드임에도 불구하고 통과할 수 있었는 듯 하다...)

#include <string>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;

int solution(int n, vector<vector<int>> edge) {
    int answer = 0;
    vector<int> dv(n,0);  // 거리에 따른 개수 기록용
    
    // 반대 간선도 넣기
    int s = edge.size();
    for(int i=0;i<s;i++){
        vector<int> temp;
        temp.push_back(edge[i][1]);
        temp.push_back(edge[i][0]);
        edge.push_back(temp);
    }
    
    sort(edge.begin(), edge.end()); // 출발 정점 기준 정렬
    vector<bool> check(n+1); // 방문 체크용
    
    // bfs를 통해 가장 먼 거리의 노드들 추가
    queue<pair<int,int>> q; // index, 거리
    q.push(pair<int,int>(1,1));
    check[1] = true; // visit
    
    // BFS
    while(!q.empty()){
        pair<int,int> now_p = q.front();
        int now = now_p.first; // 현재 경로
        int now_d = now_p.second; // 현재 거리
        q.pop();
        // 갈 수 있고 가지 않은 곳들 추가
        for(int i=0;i<edge.size();i++){
            if(edge[i][0] == now && !check[edge[i][1]]){
                q.push(pair<int,int>(edge[i][1], now_d+1));
                check[edge[i][1]] = true; // visit
                dv[now_d]++; // 거리마다 기록
            }
        }
    }
    
    // 가장 멀리 떨어져 있는 노드 수
    reverse(dv.begin(), dv.end());
    for(int i=0;i<dv.size();i++)
        if(dv[i]!=0)
            return dv[i];
}