[프로그래머스, C++] 가장 먼 노드

문제 링크

코딩테스트 연습 - 가장 먼 노드

 

 

 

풀이

문제가 한 노드에서 모든 노드의 최단 거리를 구하는 문제로 BFS로 바로 방문을 검사하며 구현하였다.

 

// init

1. 큐 선언

2. 방문 배열 선언

3. 그래프(multimap) 선언

4. 1번 노드로부터 최단 거리 배열 선언

 

// init(Graph)

파라미터로 주어진 edge를 순회하면서 multimap에 양방향으로 추가한다.

 

// process(BFS)

1. 먼저 1번 노드와 연결된 노드들을 큐에 push

2. push 한 노드들은 모두 방문 처리를 한다.

3. push 한 노드들은 1번 노드로부터 최단 거리를 1로 한다.

4. 노드 1 방문 처리

5. 큐에 원소가 남아있지 않을 때까지 반복문을 돌리면서 front에 있는 원소(cur)와 연결된 노드(next)들을 큐에 추가한다.

단, 방문을 검사하고 방문하지 않았다면, 1) 방문 처리, 2) 최단 거리 갱신(1번 노드로부터 cur까지의 최단거리 + 1) 한다.

 

// end

1. <algorithm>의 max_element를 이용하여 최단 거리 최댓값을 골라낸다.

2. 1번 노드로부터 최단 거리 배열에서 최단 거리 최댓값과 같으면 answer++로 갯수를 증가시킨다.

 

 

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

using namespace std;

// n개의 노드가 있는 그래프
// 1~n
// 1번 노드에서 가장 멀리 떨어진 노드의 갯수
// 최단 경로로 이동했을 때 간선의 개수가 가장 많은 노드

// 노드의 개수 n
// 간선 정보 2차원 배열 edge

int solution(int n, vector<vector<int>> edge) {
    int answer = 0;
    
    // init
    queue<int> q;               // for BFS
    vector<bool> visit(n+1, false);         // 방문 검사
    multimap<int, int> graph;           // 그래프
    vector<int> dist(n+1, 0);           // 노드 1에서부터 최단 거리
    
    // init(Graph)
    for(int i=0; i<edge.size(); i++){
        graph.insert(make_pair(edge[i][0], edge[i][1]));
        graph.insert(make_pair(edge[i][1], edge[i][0]));
    }
    
    // process(BFS)
    for(auto iter=graph.lower_bound(1); iter!=graph.upper_bound(1); iter++){
        int cur = iter->second;
        visit[cur] = true;      // 방문
        dist[cur] = 1;        // 1번과 연결된 노드들은 거리 1
        q.push(cur);           // 1과 연결된 노드들 push
    }
    visit[1] = true;        // 1은 방문
    while(!q.empty()){
        int cur = q.front();
        q.pop();
        for(auto iter=graph.lower_bound(cur); iter!=graph.upper_bound(cur); iter++){
            int next = iter->second;
            if(visit[next]) continue;           // 방문했으면 continue
            visit[next] = true;         // 방문
            dist[next] = dist[cur]+1;         // 거리 1 추가
            q.push(next);           // 다음 노드 추가
        }
    }
    
    // end
    int max = *max_element(dist.begin(), dist.end());       // max값
    for(int i=1; i<dist.size(); i++){
        if(max != dist[i]) continue;
        answer++;           // max값과 같을 경우에만 노드 개수 증가
    }
    
    return answer;      // 1번 노드로부터 가장 멀리 떨어진 노드가 몇 개인지 리턴
}