문제 링크
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 |