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

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

프로그래머스

 

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

int solution(int n, vector<vector<int>> edge) {
    int answer = 0;
    
    vector<vector<int>> graph(n+1);
    vector<int> dist(n+1,-1);
    queue<int> q;
    
    for(auto& item : edge)
    {
        graph[item[0]].push_back(item[1]);
        graph[item[1]].push_back(item[0]);
    }
    
    q.push(1);
    dist[1]=0;
    
    while(!q.empty())
    {
        int cur = q.front();
        q.pop();
        
        for(int neighbor : graph[cur])
        {
            if(dist[neighbor]==-1)
            {
                dist[neighbor]= dist[cur]+1;
                q.push(neighbor);
            }
        }
    }
    int maxNum=0;
    for(int i=1;i<n+1;i++)
    {
        if(maxNum<dist[i])
        {
            maxNum=dist[i];
            answer=1;
        }
        else if(dist[i]==maxNum)
            answer++;
    }

    
    return answer;
}

이 문제는 그래프가 주어지면 1번노드에서 가장 먼노드가 몇개 있는지 리턴하는 문제이다. 

 

최단경로를 구해서 가장 먼노드의 거리를 알아내고 그 거리인 노드가 몇개인지를 파악해야 한다. 

 

여기서는 BFS를 통해서 최단경로를 구한다. 

왜 BFS냐면 가중치가 없는 그래프이기 때문이다. 

1에서 연결된 이전 노드까지의 거리 + 1이 1에서 현재노드까지의 최단 거리가 된다. 

 

그래서 BFS를 사용해서 최단경로를 구할 수 있다.

만약 가중치가 있는 그래프라면 단순히 바로 직전의 연결된노드 뿐만 아니라 모든 노드에서의 경로를 확인해서 가중치가 적은 노드를 구하는 다익스트라 알고리즘을 사용해야한다. 

 

그래서 여기서는 BFS를 사용한다. 

vector<vector<int>> graph(n+1);
    vector<int> dist(n+1,-1);
    queue<int> q;
    
    for(auto& item : edge)
    {
        graph[item[0]].push_back(item[1]);
        graph[item[1]].push_back(item[0]);
    }

graph를 위한 이중 벡터와 거리를 저장할 dist, BFS를 위한 q를 생성하고 주어진 edge를 이중벡터에 그래프로 옮긴다. 

 

q.push(1);
    dist[1]=0;
    
    while(!q.empty())
    {
        int cur = q.front();
        q.pop();
        
        for(int neighbor : graph[cur])
        {
            if(dist[neighbor]==-1)
            {
                dist[neighbor]= dist[cur]+1;
                q.push(neighbor);
            }
        }
    }

1번노드가 기준이기 때문에 큐에 1번노드를 넣어놓고 dist[1]을 0으로 한다. 

여기서 dist[1]은 1번에서 1번까지의 거리를 나타낸다. 

dist가 1차원인 이유는 1번노드부터의 길이만 구하면되고 또 가중치가 없는 그래프이기 때문이다. 

dist[2]는 1->2까지의 최단길이이다. 

 

큐에서 하나를 꺼내 인접노드 중 방문하지 않은 노드에 길이를 +1해서 저장후 큐에 넣는다. 

 

이해가 가지 않는다면  BFS를 공부해봐야한다.

 

int maxNum=0;
    for(int i=1;i<n+1;i++)
    {
        if(maxNum<dist[i])
        {
            maxNum=dist[i];
            answer=1;
        }
        else if(dist[i]==maxNum)
            answer++;
    }

가장 먼 노드가 몇개인지 구하는 for문이다. 

만약 최대길이가 갱신된다면 answer를 1로 초기화하고 

그렇지 않고 최대길이와 동일하다면 +1을한다. 

 

위 코드는 chatgpt를 통해서 배운코드이다. 

원래는

int maxNum=0;
    for(int i=1;i<n+1;i++)
    {
        if(maxNum<dist[i])
        {
            maxNum=dist[i];
        }
    }
    
    for(int i=1;i<n+1;i++)
    {
    	if(maxNum==dist[i])
        	answer++;
	}

이런식으로 for문을 두번돌며 최댓값을 구한 후, 그와 동일한 것의 개수를 구했다.

하지만 위의 코드처럼 for문을 한번만 돌며 동시에 처리가 가능하다는 것을 배웠다. 

이 같은 알고리즘은 빈번히 등장하기 때문에 익혀놔야겠다.