<Programmers> Graph, BFS_가장 먼 노드 c++
3963 단어 GraphprogrammersBFSalgorithmBFS
💡Idea
- 주어진 양방향 간선을 인접 리스트 그래프로 만들어 준다
- 시작 정점 1에서부터 인접한 노드들 중 방문하지 않은 정점들을 queue에 넣어주며 bfs로 탐색한다
- 해당 정점의 방문 거리는 이전 정점의 방문 거리+1 이다
✏️Solution
- 양방향 인접 리스트 만들기
(어차피 distance를 이용해 이미 방문한 정점인지 아닌지 확인 할 것이기 때문에 중복 방문할 일은 없다)
vector<vector<int>> twoEdge(50001);
//make two-way edge
for (int i=0; i<edge.size(); i++) {
int n1=edge[i][0];
int n2=edge[i][1];
twoEdge[n1].push_back(n2);
twoEdge[n2].push_back(n1);
}
- queue에 1을 먼저 넣고 1에서 인접한 정점 순차 탐색
void bfs (int start) {
queue<int> q;
q.push(start);
while (!q.empty()) {
int cur=q.front();
q.pop();
for (int i=0; i<twoEdge[cur].size(); i++) {
// 처음 cur==1
//twoEdge[1] 즉, 1과 인접한 정점들 중 한 번도 방문한 적 없는 점들을
//queue에 넣고 해당 점까지 거리는 현재 거리 +1을 해줌
// =>dist[newNode]=dist[cur]+1
}
}
}
🔖Source Code
#include <string>
#include <vector>
#include <queue>
using namespace std;
const int MAX=50001;
int maxCnt = 0;
vector<int> dist;
vector<vector<int>> twoEdge(50001);
void bfs (int start) {
queue<int> q;
q.push(start);
while (!q.empty()) {
int cur=q.front();
q.pop();
for (int i=0; i<twoEdge[cur].size(); i++) {
int node=twoEdge[cur][i];
// adj node is not visited and not 1
if (dist[node]==0 && node!=1) {
dist[node]=dist[cur]+1;
q.push(node);
if (dist[node]>maxCnt)
maxCnt=dist[node];
}
}
}
}
int solution(int n, vector<vector<int>> edge) {
int answer=0;
dist=vector<int> (n+1);
//make two-way edge
for (int i=0; i<edge.size(); i++) {
int n1=edge[i][0];
int n2=edge[i][1];
twoEdge[n1].push_back(n2);
twoEdge[n2].push_back(n1);
}
bfs(1);
for (int i=1; i<=n; i++)
if (maxCnt==dist[i])
answer++;
return answer;
}
Author And Source
이 문제에 관하여(<Programmers> Graph, BFS_가장 먼 노드 c++), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@kimmy/Programmers-Graph-BFS가장-먼-노드-c저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)