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

문제 설명

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

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

제한사항

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

입출력 예

nvertexreturn

6

[[3, 6], [4, 3], [3, 2], [1, 3], [1, 2], [2, 4], [5, 2]]

3

입출력 예 설명

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

 

 

 

문제 풀이

그래프 문제 중 가장 쉬운 문제이다. 전혀 꼬아 놓은 것도 없는...

그런데 그래프 자체가 너무 오랜만이라 푸는데 시간이 걸렸다.

문제를 풀기전 간단한 복습을 하고 vector와 bfs를 이용해 문제를 풀기로 했다.

다음은 할 일 정리라기 보다는 그래프가 (거의) 2년 만인 나를 위한 단계이다.

1. 노드 1에 연결된 모든 노드 출력 ( 3, 2, 4, 5, 6)
2. 1에 더해 각 노드까지의 거리 추가 출력
3. 제일 먼거리의 노드의 갯수 세기

1. 노드 1에 연결된 모든 노드 출력 ( 3, 2, 4, 5, 6)

처음에 BFS를 재귀로 구현하고자 함수로 따로 빼려고 했는데... 타입에러들의 압박으로 포기했다...
씨플플 진짜 싪어!

1번을 solution 함수 안에 그냥 반복문으로 구현하는건 어렵지 않았다.

int solution(int n, vector<vector<int> > edge)
{
    int answer = 0;
    vector<int> graph[n + 1];
    queue<int> q;
    vector<bool> visited(20001, false);

    for (auto e : edge)
    {
        graph[e[0]].push_back(e[1]);
        graph[e[1]].push_back(e[0]);
    }

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

    while (!q.empty())
    {
        int node = q.front();
        cout << "visit node " << node << endl;
        for (int n : graph[node])
            if (!visited[n])
            {
                visited[n] = true;
                q.push(n);
            }
        q.pop();
    }

    return answer;
}

 

2. 1에 더해 각 노드까지의 거리 추가 출력

이게 좀 생각하기가 까다로웠는데, 처음엔 1 / 3, 2 / 6, 4, 5 로 끊어줘야 겠다고만 생각을 하니 도저히 방법을 모르겠어서, 다른 사람 코드를 참고 했다.

방법은 간단하다. distance 배열을 만들고 (모든 원소 0으로 생성) 큐에 넣으려는 노드(방문할 예정인 노드)의 거리를 현재 노드의 거리(시작노드에서 현재 노드까지의 거리) 에 1을 더해서 넣어주면 된다.

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

    for (auto e : edge)
    {
        graph[e[0]].push_back(e[1]);
        graph[e[1]].push_back(e[0]);
    }

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

    while (!q.empty())
    {
        int node = q.front();
        for (int n : graph[node])
            if (!visited[n])
            {
                visited[n] = true;
                distance[n] = distance[node] + 1;
                q.push(n);
            }
        q.pop();
    }

    return answer;
}

 

3. 제일 먼거리의 노드의 갯수 세기

제일 쉽다. distance 배열을 내림차순으로 정렬하고 첫 번 째 원소의 값과 같은 값을 가지는 원소들의 갯수를 세면 된다.

compare 함수를 굳이 만들지 않고 greater<int>()를 사용하면 좋다.

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

    for (auto e : edge)
    {
        graph[e[0]].push_back(e[1]);
        graph[e[1]].push_back(e[0]);
    }

    q.push(1);
    visited[1] = true;
    
    while (!q.empty())
    {
        int node = q.front();
        for (int n : graph[node])
            if (!visited[n])
            {
                visited[n] = true;
                distance[n] = distance[node] + 1;
                q.push(n);
            }
        q.pop();
    }

    sort(distance.begin(), distance.end(), greater<int>());

    for (int d : distance)
        if (d == distance[0])
            ++answer;
    
    return answer;
}

 

 

 

최종 코드

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

using namespace std;

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

    for (auto e : edge)
    {
        graph[e[0]].push_back(e[1]);
        graph[e[1]].push_back(e[0]);
    }

    q.push(1);
    visited[1] = true;
    
    while (!q.empty())
    {
        int node = q.front();
        for (int n : graph[node])
            if (!visited[n])
            {
                visited[n] = true;
                distance[n] = distance[node] + 1;
                q.push(n);
            }
        q.pop();
    }

    sort(distance.begin(), distance.end(), greater<int>());

    for (int d : distance)
        if (d == distance[0])
            ++answer;
    
    return answer;
}

 

디버깅 용 코드

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

using namespace std;

void print_vector(vector<int> vec)
{
    for (int v : vec)
        cout << v << " ";
    cout << endl;
}

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

    for (auto e : edge)
    {
        graph[e[0]].push_back(e[1]);
        graph[e[1]].push_back(e[0]);
    }

    q.push(1);
    visited[1] = true;
    
    while (!q.empty())
    {
        int node = q.front();
        for (int n : graph[node])
            if (!visited[n])
            {
                visited[n] = true;
                distance[n] = distance[node] + 1;
                q.push(n);
            }
        q.pop();
    }

    sort(distance.begin(), distance.end(), greater<int>());

    for (int d : distance)
        if (d == distance[0])
            ++answer;
    
    return answer;
}

int main()
{
    vector<vector<int> > edge = {{3, 6}, {4, 3}, {3, 2}, {1, 3}, {1, 2}, {2, 4}, {5, 2}};
    cout << solution(6, edge);
    return 0;
}

 

 

 

다른 사람의 코드

일등 코드 봤는데 나와 로직이 같아서 생략