프로그래머스 - 가장 먼 노드 (C++)

Pixabay로부터 입수된 krzysztof-m님의 이미지 입니다.

 

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

프로그래머스

 이번 문제는 그래프의 노드 사이의 연결 상태가 주어졌을 때, 1번 노드에서 가장 멀리 떨어져 있는 노드의 개수가 몇 개인지 알아내는 문제이다. 예를 들어, 예제에서는 1번 노드를 기준으로 2번 노드, 3번 노드는 거리가 1만큼 떨어져 있다. 그리고 4번 노드, 5번 노드, 6번 노드는 2만큼 떨어져 있다. 그렇기에 가장 멀리 떨어진 거리는 2이고 이에 해당하는 노드의 개수는 3이다. 

 1번 노드에서 각 노드까지의 떨어진 거리를 구하는 방법은 다양할 것이다. 하지만 이번에는 이 문제를 풀기 위해 BFS를 이용하였다. BFS를 이용하면 각 노드에서 특정 노드까지의 최단 길이를 구할 수 있기에 이를 이용하였다. 대략적인 과정과 작성한 코드는 다음과 같다.

1. 우선 주어진 vertex를 노드별로 정리한다. 예를 들어, [1, 3]은 1번 노드와 3번 노드가 연결되어 있다는 뜻이므로 links[1]에 3을, links[3]에 1을 push_back한다. (vector links[x]: x번 노드와 연결되어 있는 노드들이 담겨 있는 vector)
2. 1번 노드를 시작 노드로 삼은 후, queue<pair<int, int>>에 { 1번 노드, 0 }을 push한다. 이 때, 큐의 자료형은 pair<int, int>이고 pair의 first에는 노드가, second에는 그 노드까지의 거리가 저장된다. (1번 노드는 시작 노드이므로 거리가 0이다.)
3. queue에서 pop을 한 후, 현재 노드까지의 거리와 현재까지의 최대 거리를 비교해본 후 답을 갱신한다.
4. 현재 노드와 연결된 모든 노드들을 검사한다. 만약 연결된 노드가 방문하지 않은 노드라면 방문했음을 기록한 후, queue에 { 연결된 노드, 현재까지 거리 + 1 }을 push한다. 

#include <string>
#include <vector>
#include <queue>
#define MAX 20001
using namespace std;

int maxDist = 0;
int answer = 0;
bool visited[MAX];
vector<int> links[MAX];

void Check(int startNode)
{
    queue<pair<int, int>> q;
    q.push({ startNode, 0 });
    visited[startNode] = true;
    
    while(!q.empty())
    {
        int curNode = q.front().first;
        int curDist = q.front().second;
        q.pop();
        
        if (maxDist == curDist)
            ++answer;
        else if (maxDist < curDist)
        {
            maxDist = curDist;
            answer = 1;
        }
        
        for (int i = 0; i < links[curNode].size(); ++i)
        {
            int nxtNode = links[curNode][i];
            
            if (visited[nxtNode] == false)
            {
                visited[nxtNode] = true;
                q.push({ nxtNode, curDist + 1 });
            }
        }
    }
}

int solution(int n, vector<vector<int>> edge) {
    for (int node = 0; node < MAX; ++node)
        visited[node] = false;
    
    for (int i = 0; i < edge.size(); ++i)
    {
        int nodeA = edge[i][0];
        int nodeB = edge[i][1];
        
        links[nodeA].push_back(nodeB);
        links[nodeB].push_back(nodeA);
    }
    
    Check(1);
    
    return answer;
}

 

---

BFS에 대해 잘 설명되어 있는 글

https://blog.naver.com/ndb796/221230944971