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

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

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

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

 

문제 설명

n개의 노드가 있는 그래프가 있습니다. 각 노드는 1부터 n까지 번호가 적혀있습니다. 1번 노드에서 가장 멀리 떨어진 노드의 갯수를 구하려고 합니다. 가장 멀리 떨어진 노드란 최단경로로 이동했을 때 간선의 개수가 가장 많은 노드들을 의미합니다.

노드의 개수 n, 간선에 대한 정보가 담긴 2차원 배열 vertex가 매개변수로 주어질 때, 1번 노드로부터 가장 멀리 떨어진 노드가 몇 개인지를 return 하도록 solution 함수를 작성해주세요.

제한사항

• 노드의 개수 n은 2 이상 20,000 이하입니다.
• 간선은 양방향이며 총 1개 이상 50,000개 이하의 간선이 있습니다.
• vertex 배열 각 행[a, b]는 a번 노드와 b번 노드 사이에 간선이 있다는 의미 입니다.

입출력 예

n	vertex	return
6	[[3, 6], [4, 3], [3, 2], [1, 3], [1, 2], [2, 4], [5, 2]]	3

입출력 예 설명

예제의 그래프를 표현하면 아래 그림과 같고, 1번 노드에서 가장 멀리 떨어진 노드는 4,5,6번 노드입니다.

 

---

풀이 과정

그래프 문제가 생소하지만 그래도 일단 최단거리라는 키워드로 인해서 bfs를 활용할 수 있을 것만 같아서 접근!

 

1. dfs식으로 접근했다가 재귀 메소드에서 값 넘기는 부분에서 계속 꼬여서 다시 queue를 활용하는 bfs로 빠르게 바꿨다.
2. 이전에 계속 dp 문제만 풀다보니까 dp 처럼 최단 거리를 계속 저장해둘 distance 라는 1차원 벡터를 활용하였다.
3. 이런 그래프 타입의 문제들에서는 conInfo 라는 변수처럼 각 연결되어 있는 시작 노드와 끝 노드들을 넣어 연결 정보들을 저장해야 한다.
4. 그 후에는 1번 노드에서 가장 먼 노드를 알아야 하고 그 갯수를 알아야 하기 때문에 queue에 1을 push 해주고 1번 노드로부터 연결되어 있는 노드들의 방문 여부를 체크하면서 distance 변수에 +1 씩 해주면서 bfs 탐색을 하다보면 최단거리가 나온다.
5. 마지막으로 그 최단거리가 담겨있는(distance) 벡터를 내림차순 정렬을 통해서 distance[0] 과 같은 거리에 있는 값들을 카운팅 해주면 가장 먼 노드들의 갯수가 된다!

 

코드

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

using namespace std;

bool comp(int a, int b) {
    return a > b;
}

int solution(int n, vector<vector<int>> edge) {
    int answer = 0;
    vector<vector<int>> conInfo(n+1);
    vector<bool> visited(n+1, false);
    vector<int> distance(n+1, 0);
    queue<int> q;


    for(int i = 0 ; i < edge.size(); i++) {
        int start = edge[i][0];
        int end = edge[i][1];

        conInfo[start].push_back(end);
        conInfo[end].push_back(start);
    }

    q.push(1);
    visited[1] = true;

    while(!q.empty()) {
        int startNode = q.front();
        q.pop();

          // startNode와 연결된 노드들 방문
        for(int i = 0; i < conInfo[startNode].size(); i++) {
            int endNode = conInfo[startNode][i];
            if(!visited[endNode]) {
                visited[endNode] = true;

                distance[endNode] = distance[startNode] + 1;
                q.push(endNode);
            }
        }
    }

    sort(distance.begin(), distance.end(), comp);

    for(auto d : distance) {
        if(d == distance[0])
            answer++;
    }


    return answer;
}