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

링크

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

프로그래머스

풀이

 

1번 노드로부터 가장 멀리 떨어진 노드가 몇 개인지를 구하는 문제이다.

 

문제를 보았을 때 DFS, BFS 둘 중에 한 개로 탐색을 해야 된다는 것을 알 수 있습니다.

그런데 일단 노드간에 사이클이 있기 때문에

 

DFS를 이용하여 탐색을 하게되면 1 - 3 - 4 - 2 - 5와 같이 탐색을 진행할 수 있어 가장 멀리 떨어진 노드를 구하기가 쉽지 않아 집니다.

 

그러므로 BFS 탐색을 이용하여 노드를 하나씩 탐색하면 1번 으로부터 가장 먼 노드의 갯수를 구할 수 있습니다.

 

#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>

#define SIZE 20010
using namespace std;
vector<int> arr[SIZE];
bool visited[SIZE];
int solution(int n, vector<vector<int>> edge) {
	for (auto e : edge) {
		arr[e[0]].push_back(e[1]);
		arr[e[1]].push_back(e[0]);
	}

	queue<pair<int,int>> q;
	q.push(make_pair(1,0));
	
	pair<int, int> res = { 0,0 };
	while (!q.empty() ){
		pair<int, int> h = q.front(); q.pop();
		visited[h.first] = true;

		for (auto next : arr[h.first]) {
			if (visited[next] == true)
				continue;

			pair<int, int> n = { next, h.second + 1 };

			if (res.first == n.second)
				res.second++;
			else if (res.first < n.second) {
				res.first = n.second; res.second = 1;
			}

			visited[next] = true;
			q.push(n);
		}
	}
	return res.second;
}