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

2025. 5. 15. 16:41·개발/알고리즘

문제 링크

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

 

프로그래머스

SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프

programmers.co.kr

 

 

코드 구현

#include <iostream>
#include <vector>
#include <string>
#include <queue>

using namespace std;

vector<vector<int>> graph;
vector<int> visited;
queue<int> q;

void bfs(int start)
{
    visited[start] = 1;
    q.push(1);

    while (!q.empty())
    {
        int now = q.front();
        q.pop();

        for (int neighbor : graph[now])
        {
            if (!visited[neighbor])
            {
                visited[neighbor] = 1 + visited[now];
                q.push(neighbor);
            }
        }
    }

}

int solution(int n, vector<vector<int>> edge) 
{
    int answer = 0;
    graph.resize(n + 1);
    visited.resize(n + 1, 0);

    // 그래프 생성
    for (int i = 0; i < edge.size(); i++)
    {
        int node = edge[i][0];
        int neighbor = edge[i][1];

        graph[node].push_back(neighbor);
        graph[neighbor].push_back(node);
    }

    bfs(1);

    // 최단 경로 = 최댓값
    int maxValue = 0;
    if (!visited.empty())
    {
        maxValue = *max_element(visited.begin(), visited.end());
    }

    // 최단 경로 개수 구하기
    answer = count(visited.begin(), visited.end(), maxValue);

    return answer;
}

 

 

해결 방법

우선 최단 경로를 찾아야 하므로 bfs로 문제를 접근했고, 한 노드에서 이웃 노드로 이동할 때마다 이전 노드의 값 + 1을 더해주어 거리를 계산하였다. bfs 함수가 끝나면 숫자가 가장 큰 노드가 가장 멀리 떨어져 있는 노드이므로 가장 큰 숫자를 가지고 있는 노드의 개수를 세어주면 된다.

'개발 > 알고리즘' 카테고리의 다른 글

[백준] 7576번: 토마토(C++)  (1) 2025.05.24
[백준] 1967번: 트리의 지름(C++)  (1) 2025.05.16
[프로그래머스] 길 찾기 게임(C++)  (2) 2025.05.13
[백준] 회의실 배정(C++)  (1) 2025.05.12
[백준] 평범한 배낭( C++)  (1) 2025.05.12
'개발/알고리즘' 카테고리의 다른 글
  • [백준] 7576번: 토마토(C++)
  • [백준] 1967번: 트리의 지름(C++)
  • [프로그래머스] 길 찾기 게임(C++)
  • [백준] 회의실 배정(C++)
Majangnan
Majangnan
  • Majangnan
    개발 모코코
    Majangnan
  • 전체
    오늘
    어제
    • 분류 전체보기 (66)
      • 개발 (65)
        • C# (10)
        • SQL (3)
        • Unity (8)
        • Unreal (10)
        • C++ (3)
        • Server (1)
        • DX11 (8)
        • 알고리즘 (21)
  • 블로그 메뉴

    • 홈
    • 방명록
    • 깃허브
  • 링크

  • 공지사항

  • 인기 글

  • 태그

    dx3d
    Mecanim
    C#
    3dlight
    백준
    프로그래머스
    DX11
    상속
    코딩테스트
    UnReal
    MAC
    슈팅게임
    블루프린트
    알고리즘
    언리얼
    Unity
    blueprint
    DirectX11
    c++
    sql
  • 최근 댓글

  • 최근 글

  • hELLO· Designed By정상우.v4.10.3
Majangnan
[프로그래머스] 가장 먼 노드(C++)
상단으로

티스토리툴바