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

문제

문제 설명

 

풀이

 

[풀이]

 

노드간에 길이 연결 되어 있는지 vector로 표현하고, BFS로 탐색해 나가면 되는 문제다.

 

BFS로 탐색을 하므로 처음 방문했을 때가 최단 거리인 사실을 생각하면, 단순히 BFS로 탐색하면서 이전 노드를 방문할 때 걸린 거리 + 1 을 노드에 저장하면 되는 문제다.

​

[아이디어 정리]

1. Vector를 이용해 노드간에 연결이 되어있는지 표현한다.​
2. 1번 노드부터 BFS로 방문하며 새로 방문한 노드에는 이전 노드를 방문하는데 걸린 거리 +1을 저장한다.
3. 모든 노드를 탐색한 후에는 가장 먼 노드의 거리가 얼마인지 구한 다음 가장 먼 노드의 개수를 return한다.

 

 

Code

 

 

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

vector<vector<int>> linkList;
int visited[20001]; 
int solution(int n, vector<vector<int>> edge) {
    linkList=vector<vector<int>>(n+1);
    for (int i=0; i<edge.size(); i++)
    {
        linkList[edge[i][0]].push_back(edge[i][1]);
        linkList[edge[i][1]].push_back(edge[i][0]);
    }
    fill_n(visited,20001,0);
    int nowNode=1;
    visited[1]=1;
    queue<int> BFSList;
    BFSList.push(nowNode);
    while (BFSList.size()>0)
    {
        nowNode = BFSList.front();
        BFSList.pop();
        for (int i=0; i<linkList[nowNode].size(); i++)
        {
            if (visited[linkList[nowNode][i]]==0)
            {
                visited[linkList[nowNode][i]]=visited[nowNode]+1;
                BFSList.push(linkList[nowNode][i]);
            }
        }
    }
    int maxNum=0;
    for (int i=2; i<linkList.size(); i++)
    {
        if (maxNum<visited[i])
        {
            maxNum=visited[i];
        }
    }
    int answer = 0;
    for (int i=0; i<linkList.size(); i++)
    {
        if (maxNum==visited[i])
        {
            answer+=1;
        }
    }
    return answer;
}

 

---

 

BFS만 익숙하면 쉽게 풀 수 있는 문제였다

 

프로그래머스