[프로그래머스] 가장 먼 노드

프로그래머스

코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.

programmers.co.kr

풀이

BFS를 통해 1번 노드부터 모든점들을 방문하고 가장 오래 걸린 노드들의 개수를 출력해주면 된다. 초기 입력 값으로 들어오는 edge 배열을 인접 리스트로 변환하여 풀이하였다.

코드

#include <string>
#include <vector>
#include <queue>
#include <iostream>
#include <algorithm>
using namespace std;
vector<vector<int>> adj;
vector<int> visited;

int bfs(){
    queue<int> q;
    q.push(1);
    visited[1] = 0;
    int ret = 0;
    while(!q.empty()){
        int cur = q.front();
        q.pop();

        for(int i=0; i<adj[cur].size(); i++){
            int next = adj[cur][i];
            if(visited[next] == -1){
                visited[next] = visited[cur] + 1;
                ret = max(ret, visited[next]);
                q.push(next);
            }
        }
    }
    return ret;
}

int solution(int n, vector<vector<int>> edge) {
    int answer = 0;
    adj = vector<vector<int>>(n+1);
    visited = vector<int>(n+1, -1);
    for(int i=0; i<edge.size(); i++){
        adj[edge[i][0]].push_back(edge[i][1]);
        adj[edge[i][1]].push_back(edge[i][0]);
    }
    int t = bfs();

    for(int i=1; i<=n; i++)
        if(visited[i] == t) answer++;
    return answer;
}