[알고리즘C++] 가장 먼 노드

오늘의 문제

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

가장 먼 노드

나의 풀이

#include <string>
#include <vector>

using namespace std;

int solution(int n, vector<vector<int>> edge) {
    
    vector<vector<int>> node(n);
    for(int i=0;i<edge.size();i++){
        node[edge[i][0]-1].push_back(edge[i][1]-1);
        node[edge[i][1]-1].push_back(edge[i][0]-1);
    }
    vector<int> go;
    bool check[20001] ={false, };
    check[0] = true;
    for(int i=0;i<node[0].size();i++){
        go.push_back(node[0][i]);
        check[node[0][i]] = true;
    }
    int answer = go.size();
    while(go.size() != 0){
        vector<int> tmp;
        for(int i=0;i<go.size();i++){
            for(int j=0;j<node[go[i]].size();j++){
                if(check[node[go[i]][j]] == false){
                    tmp.push_back(node[go[i]][j]);
                    check[node[go[i]][j]] = true;
                }
            }
        }
        if(go.size() != 0)
            answer = go.size();
        go = tmp;
    }
    return answer;
}

모범 답안

#include <string>
#include <vector>
#include<queue>
#include<iostream>
using namespace std;

int d[20001][20001];
bool visit[20001];
int dist[20001];
int solution(int n, vector<vector<int>> edge) {
    int max = 0;
    int answer = 0;
    for(int i=0;i<edge.size();i++)
    {
        d[edge[i][0]][edge[i][1]]=1;
        d[edge[i][1]][edge[i][0]]=1;
    }

    queue<int> q;
    visit[1]=true;
    q.push(1);
    dist[1]=0;
    while(!q.empty())
    {
        int first = q.front();
        q.pop();       
        for(int i=2;i<=n;i++)
        {
            if(d[first][i]==1 && !visit[i])
            {
                q.push(i);
                visit[i]=true;
                dist[i]=dist[first]+1;
                if(max<dist[i])
                {
                    max=dist[i];
                }
            }
        }
    }

    for(int i=1;i<=n;i++)
    {
        if(max==dist[i])
        {
            answer++;
        }
    }
    return answer;
}

배울 점

• 뭔가 슬럼프가 왔는지 갑자기 안풀어진다 쉬운문제로 다시 열을 올리자
• 굉장히 단순하게 풀 수 있는데 괜히 어렵게 풀려하는것 같다.
• visit과 queue만 이용해도 가볍게 풀 수 있다. 구해야하는것은 depth가 가장 깊은 노드의 개수이므로 child의 child를 구하는 depth만 같도록 구해나가면 된다.