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

< 해설 >

그래프가 사실 너비/깊이 탐색이랑 관련이 아예 없다고 할 순 없는데 그냥 보자마자 너비 우선 탐색으로 하면 되겠다 싶어서 그냥 그렇게 풀었다.. 노드는 무조건 1번에서 시작하므로 크루스칼이나 프림을 사용하지 않아도 된다고 생각했음.. 또 거리에 cost 가 없으니까 최소 신장 트리를 굳이 사용하지 않았다. 그래서 많이 풀어서 자신있는 BFS로 문제를 해결했다.

 

각 노드가 어느 노드와 연결되어있는지 정리해 준 뒤, 1 번 노드부터 시작하여 연결된 노드를 방문체크 해주며 모든 노드를 탐색해보면 된다. 그럼 진행순서가 다음과 같아진다.

• 1번 노드는 3,2 번 노드와 연결되어 잇으므로 3,2 탐색
  • 3번 노드는 6,4 번과 연결되어있으니 6,4 탐색
    • 6번은 더 갈 곳이 없음
    • 4번 노드는 2번과 연결되어 있지만 2번은 이미 방문했으므로 가지 않음
  • 2번 노드는 4,5 와 연결되어 있지만 4번은 이미 방문했으므로 가지 않음
    • 5번은 더 갈 곳이 없음

그리고 가장 먼 노드가 1번 노드와 얼마나 떨어져 있는지 알아야한다. BFS에는 가장 멀리 있는 노드나 길의 계산이 필히 가장 마지막에 계산되므로 매 업데이트마다 answer을 갱신해주는 방법을 사용했다. 그러면 BFS가 종료되고 answer에 남은 값이 저절로 가장 큰 값이 된다.

 

< 문제 >

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

 

 

< 풀이 >

#include <string>
#include <vector>
#include <queue>
#include "string.h"

using namespace std;
    
bool check[20000];

int solution(int n, vector<vector<int>> edge) {
    int answer = 0;
    memset(check, false, sizeof(check));
    vector<vector<int>> node(n+1);
    vector<int> nodeSum(n+1, 0);
    
    for(auto e : edge) // 어떤 노드가 어떤 노드와 연결되었는지 확인
    {
        node[e[0]].push_back(e[1]);
        node[e[1]].push_back(e[0]);
    }
    
    queue<pair<int,int>> task; // pair<nodeIdx, moveCount>
    task.push(make_pair(1, 1));
    check[1] = true;
    nodeSum[1] += 1;
    
    while(!task.empty())
    {
        int curIdx = task.front().first;
        int count = task.front().second;
        task.pop();
        
        for(int i=0; i< node[curIdx].size(); i++)
        {
            if(check[node[curIdx][i]] != true)
            {
                task.push(make_pair(node[curIdx][i], count + 1));
                check[node[curIdx][i]] = true;                
                nodeSum[count+1] += 1;
                answer = nodeSum[count+1];
            }
        }           
    }

    return answer;
}