C++ 프로그래머스 코딩테스트 - 가장 먼 노드 (49189)

가장 먼 노드

Level 3

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

프로그래머스

 

 

시작점으로 부터 가장 멀리 떨어져 있는 노드를 찾는 문제이다.

 

나의 풀이

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

int solution(int n, vector<vector<int>> edge)
{
	int 가장_먼_간선개수 = 0;
	map<int/*노드*/, int/*간선 개수*/> dest_count{ {1,0} };

	queue<vector<int>> q;
	q.push({ 1, 0, 0/*간선 개수*/, 1/*방향 노드*/ });

	while (!q.empty()) 
	{
		vector<int> info = q.front();
		q.pop();

		for (const auto& r : edge)
		{
			if (r[0] == info[3] || r[1] == info[3]) {
				int newNumber = r[0] == info[3] ? r[1] : r[0];

				// 이전에 방문한 노드이고, 간선 개수가 작거나 같으면 갱신 X (최단 경로를 찾아야 하므로)
				if (dest_count.find(newNumber) != dest_count.end() && dest_count.find(newNumber)->second <= info[2] + 1)
					continue;
				q.push({ r[0],r[1],  info[2] + 1, newNumber });
				dest_count[newNumber] = info[2] + 1;
				if (가장_먼_간선개수 < info[2] + 1)
					가장_먼_간선개수 = info[2] + 1;
			}
		}
	}
    
	int answer = 0;
	for (const auto& a : dest_count)
		if (a.second == 가장_먼_간선개수)
			++answer;

	return answer;
}

 

dest_count 컨테이너에 최단 경로 간선 개수를 넣어준다.