프로그래머스 문제 - 가장 먼 노드

프로그래머스 가장 먼 노드 문제 풀이를 진행하였습니다.

문제 해석

문제를 읽으면 아래와 같은 해석이 가능합니다.

n개의 노드와 양방향으로 노드들을 잇는 간선들이 주어집니다.
1번 노드로부터 가장 멀리 떨어진 노드들의 수를 구해야합니다.

노드 사이의 거리를 생각해야 합니다.

문제 풀이

제일 먼 노드들을 알아내야 하기 때문에 BFS알고리즘을 사용할 것입니다.
받아온 간선들을 트리로 저장해줍니다.
양방향인것을 까먹지 말고 생각해줍니다.

for(vector<int> v : edge)
{
    tree[v[0]].push_back(v[1]);
    tree[v[1]].push_back(v[0]);
}

1번 노드부터 차례대로 노드들의 거리를 찾아가줍니다.
최단 거리이기 때문에 한번 들린 노드는 다시 찾지 않습니다.

dist[1] = 0;
checkNode.push(1);
while(!checkNode.empty())
{
    int cur = checkNode.front();
    checkNode.pop();
    for(int i : tree[cur])
    {
        if(dist[i] == -1)
        {
            dist[i] = dist[cur] + 1;
            checkNode.push(i);
        }
    }
}

이후에 저장된 거리들 중 제일 큰 수를 찾고 몇개의 거리가 있는지 찾아줍니다.

sort(dist.begin(), dist.end(), greater<>());
int max = dist[0];
    
for(int i : dist)
{
    if(max == i)
    {
        answer++;
    }
}

전체 코드

이번 문제는 DFS의 짝궁 BFS의 작동순서 및 방식을 배우는 문제였습니다.

#include <bits/stdc++.h>
#include <string>
#include <vector>

using namespace std;

int solution(int n, vector<vector<int>> edge) {
    int answer = 0;
    vector<int> tree[20001];
    vector<int> dist(20001, -1);
    queue<int> checkNode;
    
    for(vector<int> v : edge)
    {
        tree[v[0]].push_back(v[1]);
        tree[v[1]].push_back(v[0]);
    }
    
    dist[1] = 0;
    checkNode.push(1);
    while(!checkNode.empty())
    {
        int cur = checkNode.front();
        checkNode.pop();
        for(int i : tree[cur])
        {
            if(dist[i] == -1)
            {
                dist[i] = dist[cur] + 1;
                checkNode.push(i);
            }
        }
    }
    
    sort(dist.begin(), dist.end(), greater<>());
    int max = dist[0];
    
    for(int i : dist)
    {
        if(max == i)
        {
            answer++;
        }
    }
    
    return answer;
}

출저

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