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

문제 링크입니다 : https://programmers.co.kr/learn/courses/30/lessons/49189

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

 

그래프 문제였다.

 

그래프나 트리에서 깊이별로 탐색하고 싶다면 bfs를 쓰면 된다.

 

 

 

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

using namespace std;

vector<vector<int>> adj;
vector<bool> visited;

vector<int> bfs(int start) {
    queue<int> q;
    q.push(start);
    visited[start] = true;
    
    vector<int> ret;
    
    while(!q.empty()) {
        int qSize = q.size();
        bool isFirst = true;
        for(int i = 0; i < qSize; i++) {
            int cur = q.front();
            q.pop();
            for(int j = 0; j < adj[cur].size(); j++) {
                int next = adj[cur][j];
                if(visited[next]) continue;
                if(isFirst) {
                    isFirst = false;
                    ret.clear();
                }
                visited[next] = true;
                ret.push_back(next);
                q.push(next);
            }
        }
    }
    return ret;
}

int solution(int n, vector<vector<int>> edge) {
    int answer = 0;
    
    adj.assign(n + 1, vector<int>());
    visited.assign(n + 1, false);
    
    for(int i = 0; i < edge.size(); i++) {
        int u = edge[i][0];
        int v = edge[i][1];
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    
    vector<int> result = bfs(1);
    
    answer = result.size();
    
    return answer;
}

 

 

 

개발 환경 : vscode

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~