개발기록장

가장 먼 노드

5 min read

문제 링크
난이도 : Lv. 3

문제 내용

문제 설명

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번 노드입니다.

image.png

문제 분석

한 번씩 이동하면서 거기까지의 길이를 저장해두기?

작성한 코드

#include <string>
#include <vector>
#include <algorithm>
 
using namespace std;
 
vector<int> edgeCount;
vector<vector<int>> connectList;
vector<int> nextNodes;
 
void goToNext(int currentNode, int edges)
{
    if(connectList[currentNode].size() == 0)
    {
        edgeCount[currentNode] = min(edges, edgeCount[currentNode]);
        return;
    }
    
    nextNodes.erase(find(nextNodes.begin(), nextNodes.end(), currentNode));
    
    edges++;
    
    for(int i = 0; i < connectList[currentNode].size(); i++)
    {
        nextNodes.push_back(connectList[currentNode][i]);
    }
    
    for(int i = 0; i < nextNodes.size(); i++)
    {
        goToNext(nextNodes[i], edges);
    }
}
 
 
 
int solution(int n, vector<vector<int>> edge) {
    edgeCount.assign(n, 20005);
    connectList.assign(n, {});
    
    for(auto e : edge)
    {
        connectList[e[0] - 1].push_back(e[1] - 1);
    }
    
    // make connect list done.
    
    goToNext(0, 0);
    
    sort(edgeCount.begin(), edgeCount.end());
    
    int largestCount = edgeCount.back();
    int answer = 1;
    for(int i = edgeCount.size() - 2; i > -1; i--)
    {
        if(edgeCount[i] == largestCount)
        {
            answer++;
        }
        else break;
    }
    
    
    
    return answer;
}
  • 그런데 segmentation fault 가 뜸
  • 왜일까?

Chatgpt의 분석

❌ 현재 코드 구조의 문제점 요약

문제점설명
방향 그래프만 구성문제는 무방향 그래프인데 connectList[e[0]-1].push_back(e[1]-1)만 넣었음
BFS가 아님nextNodes를 중첩 push하면서 DFS/BFS 둘 다 아닌 이상한 탐색
방문 체크 없음무한 루프 발생
재귀 깊이가 엄청 커짐n 최대 20,000 → 재귀로는 불가능
edgeCount에 거리 저장 방식도 이상함min(edges, edgeCount[current]) 이지만 nextNodes 구조상 edges 값이 비정상적으로 증가
  • 그럼 다시 짜보자
#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
 
using namespace std;
 
vector<int> edgeCount;
vector<vector<int>> connectList;
vector<int> nextNodes;
 
 
void dfs(int currentNode, int currentMove)
{
    if(edgeCount[currentNode] != -1) return;
    
    edgeCount[currentNode] = currentMove;
    currentMove++;
    
    for(int i = 0; i < connectList[currentNode].size(); i++)
    {
        nextNodes.push_back(connectList[currentNode][i]);
    }
    
    for(int i = 0; i < nextNodes.size(); i++)
    {
        dfs(nextNodes[i], currentMove);
    }
    if(nextNodes.empty()) return;
}
 
 
int solution(int n, vector<vector<int>> edge) {
    edgeCount.assign(n + 1, -1);
    connectList.assign(n + 1, {});
    
    for(auto e : edge)
    {
        connectList[e[0]].push_back(e[1]);
        connectList[e[1]].push_back(e[0]); // 양방향
    }
    
    dfs(1, 0);
 
    for(auto c : edgeCount)
    {
        cout << c << " ";
    }
    cout << endl;
    
    return 0;
    // return answer;
}

  • 그래도 틀렸댄다…

  • 심지어 bfs를 dfs라고 씀

  • pop도 안함

  • 다시 시도.

#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
#include <queue>
 
using namespace std;
 
vector<vector<int>> connectList;
vector<int> dist;
queue<int> nextNodes;
 
 
int solution(int n, vector<vector<int>> edge) {
    dist.assign(n + 1, -1);
    connectList.assign(n + 1, {});
    
    for(auto e : edge)
    {
        connectList[e[0]].push_back(e[1]);
        connectList[e[1]].push_back(e[0]); // 양방향
    }
    
    dist[1] = 0;
    nextNodes.push(1);
    
    while(!nextNodes.empty())
    {
        int currentNode = nextNodes.front(); 
        nextNodes.pop();
        
        for(auto c : connectList[currentNode])
        {
            // c는 현재 노드와 연결된 노드들
            if(dist[c] == -1)
            {
                dist[c] = dist[currentNode] + 1;
                nextNodes.push(c); // c도 방문해야 함
            }
        }
    }
    
//     for(auto d : dist)
//     {
//         cout << d << " ";
//     }
    
//     cout << endl;
    
    
    sort(dist.begin(), dist.end());
    int maxDist = dist[dist.size() - 1];
    int answer = 1;
    
    for(int i = dist.size() - 2; i > -1 ; i--)
    {
        if(dist[i] == maxDist)
        {
            answer++;
        }
    }
    
    return answer;
    
}

그래프 뷰