[Programmers]그래프 > 가장 먼 노드(c++)

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

코딩테스트 연습 - 가장 먼 노드

 

BFS로, 모든 노드를 방문 했을 때 남아있는 q의 사이즈를 출력했다.

 

1. edge의 값들을 graph안에 연결된 노드들을 추가함

2. 1부터 시작하므로, 맨처음엔 q에 1을 push

3. 현재 q의 사이즈만큼 pop을 해주면서 q의 top (현재 1)과 연결되어있는 노드 graph[top]안의 원소들을 모두 push

4. 추가한 원소들은 모두 방문 표시(isVisited[top][i]=true)

5.  3~4번을 isVisited가 모두 true가 될때까지 반복

6. 현재 남아있는 q의사이즈를 출력

 

 

 

---

main포함 코드(c++)

#include <string>
#include <vector>
#include <queue>
#include <algorithm>
#include <cstring>
using namespace std;

int answer = 0;
void BFS(int n, vector<vector<int>> graph, bool isVisited[], int V){
    if(isVisited[V]) return;
    isVisited[0] = true;
    isVisited[V] = true;

    queue<int> q;
    q.push(V);
    int top = q.front();
    
    int cnt = 0;
    while (answer != q.size()) {
        if(count(isVisited, isVisited+n+1, true) == n+1) { answer = q.size(); break; }
        
        int q_size = q.size();
        
        cnt++;
        while (q_size--) {
            top = q.front();
            isVisited[top] = true;
            q.pop();
            for(int i=0;i<graph[top].size();i++) if(!isVisited[graph[top][i]]) { isVisited[graph[top][i]]=true; q.push(graph[top][i]);}
        }
    }
}

int solution(int n, vector<vector<int>> edge) {
  
    bool isVisited[n+1];
    memset(isVisited, false, n+1);
    vector<vector<int>> graph(n+1);
    for(int i=0;i<edge.size();i++){
            graph[edge[i][0]].push_back(edge[i][1]);
            graph[edge[i][1]].push_back(edge[i][0]);
    }
    for(int i=0;i<n+1;i++)sort(graph[i].begin(), graph[i].end());
    
    BFS(n, graph,isVisited ,1);
    return answer;
}

int main(){
    
    int n=4;
//    vector<vector<int>> edge = {{3, 6}, {4, 3}, {3, 2}, {1, 3}, {1, 2}, {2, 4}, {5, 2}};
    vector<vector<int>> edge = {{1, 2}, {1, 3}, {2, 3}, {2, 4}, {3, 4}};
    
    solution(n, edge);
    return 0;
}