[Programmers 코딩테스트 고득점 Kit] 가장 먼 노드

문제 링크입니다: https://programmers.co.kr/learn/courses/30/lessons/49189

코딩테스트 연습 - 가장 먼 노드

BFS를 이용하여 푸는 문제였습니다.

 

알고리즘은 아래와 같습니다.

1. 양방향 그래프를 입력받습니다.

2. 1번 노드로부터 BFS를 진행하는데

2.1 제일 먼 거리가 갱신될 경우 기존에 제일 멀었던 노드들이 속해있는 벡터를 지우고 다시 해당 노드를 벡터에 추가해주고

2.2 현재 노드로부터 1번 노드까지의 거리가 제일 먼 거리와 동일할 경우 벡터에 해당 노드를 추가해줍니다.

3. 노드의 개수를 구해야 하므로 벡터의 크기를 반환해줍니다.

 

	#include <iostream>
	#include <string>
	#include <vector>
	#include <queue>
	#include <algorithm>
	using namespace std;
	const int MAX = 20000 + 200;
	int longestDistance;
	bool visited[MAX];
	vector<int> nodes;
	vector<int> graph[MAX];
	typedef struct
	{
	int idx;
	int distance;
	} Node;
	int solution(int n, vector<vector<int>> edge) {
	for (int i = 0; i < edge.size(); i++)
	{
	int u = edge[i][0];
	int v = edge[i][1];
	graph[u].push_back(v);
	graph[v].push_back(u);
	}
	queue<Node> q;
	q.push({ 1, 0 });
	visited[1] = true;
	int longestDistance = 0;
	while (!q.empty())
	{
	Node cur = q.front();
	q.pop();
	if (cur.distance == longestDistance)
	{
	nodes.push_back(cur.idx);
	}
	if (cur.distance > longestDistance)
	{
	longestDistance = cur.distance;
	nodes.clear();
	nodes.push_back(cur.idx);
	}
	for (int i = 0; i < graph[cur.idx].size(); i++)
	{
	int next = graph[cur.idx][i];
	if (visited[next])
	{
	continue;
	}
	visited[next] = true;
	q.push({ next, cur.distance + 1 });
	}
	}
	return nodes.size();
	}
	int main(void)
	{
	int n = 6;
	vector<vector<int>> edge = {
	{3, 6},
	{4, 3},
	{3, 2},
	{1, 3},
	{1, 2},
	{2, 4},
	{5, 2}
	};
	cout << solution(n, edge) << "\n";
	return 0;
	}

view raw .cpp hosted with ❤ by GitHub

 

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~