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

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

using namespace std;

int BFS(int n, vector<vector<int>> &temp);

int solution(int n, vector<vector<int>> edge) {
    int answer = 0;
    vector<vector<int>> temp(n + 1);	//1~n이라 +1
        
    for(int i = 0; i < edge.size(); i++)
    {
        temp[edge[i][0]].push_back(edge[i][1]);	//양방향으로 저장
        temp[edge[i][1]].push_back(edge[i][0]);
    }
    
    answer = BFS(n, temp);	//개수 반환
    
    return answer;
}

int BFS(int n, vector<vector<int>> &temp)
{
    queue<pair<int,int>> q;	//다음 방향 저장
    q.push({1, 0});	//처음노드 지정
    int nodeCount = 0;	//먼 것의 개수
    int maxLen = 0;	//먼 길이
    vector<bool> visited(n + 1);	//1~n의 방문사항
    visited[1] = true;	//1은 처음이니 방문 true
    
    while(!q.empty())
    {
        int currNode = q.front().first;
        int currLen = q.front().second;
        q.pop();
        
        if(maxLen == currLen)	//제일 길이가 긴것과 길이가 같으면 카운트
            nodeCount++;
        else if(maxLen < currLen)	//더 크다면 개수1과 maxlen 현재길이로
        {
            nodeCount = 1;
            maxLen = currLen;
        }
        
        
        for(int j = 0; j < temp[currNode].size(); j++)	//현재 노드에서 갈 수 있는 곳 탐색
        {
            if(visited[temp[currNode][j]] == false)
            {
                visited[temp[currNode][j]] = true;
                q.push({temp[currNode][j], currLen + 1});	//다음노드는 현재노드의 +1길이
            }
        }
    }
    
    
    return nodeCount;
}

 

풀이

1. 전형적인 BFS문제이다.
2. 그런데 vertex를 단방향으로 준다.
3. 간선은 양방향이라니까 단방향으로 받은 vertex를 양방향으로 만든 리스트를 하나 만든다.
4. 그것으로 BFS하면서 제일 먼 것의 개수를 카운트해준다.

 

 

문제를 잘 읽어보자!