(c++)프로그래머스 코딩테스트 연습 - 가장 먼 노드

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

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

[풀이]

카테고리는 bfs가 아닌 그래프지만 bfs최단경로 찾기로 풀 수 있는 문제였다. 

1번 노드에서 다른 모든 노드로 가는 최단경로의 길이를 bfs로 찾은 다음 그 값이 가장 큰 노드의 개수를 세어주었다.

#include <string>
#include <vector>
#include <queue>
#include <cstring>//memset

using namespace std;
const int Max = 20001;

int dist[Max];
vector<int>Graph[Max];

//각 노드까지의 최단경로 길이 구하기
void bfs() {
	memset(dist, -1, sizeof(dist));
	queue<int>q;
	dist[1] = 0;
	for (int i = 0; i < Graph[1].size(); i++) {
		q.push(Graph[1][i]);
		dist[Graph[1][i]] = 1;
	}
	while (!q.empty()) {
		int x = q.front();
		q.pop();
		for (int i = 0; i < Graph[x].size(); i++) {
			if (dist[Graph[x][i]] >= 0)
				continue;
			dist[Graph[x][i]] = dist[x] + 1;
			q.push(Graph[x][i]);
		}
	}
}

//가장 멀리 떨어진 노드 개수 구하기
int getMax(int n) {
	int M = -1;
	int cnt = 0;
	for (int i = 1; i <= n; i++) {
		if (dist[i] > M) {
			cnt = 1;
			M = dist[i];
		}
		else if (dist[i] == M) {
			cnt++;
		}
	}
	return cnt;
}

int solution(int n, vector<vector<int>> edge) {
	int answer = 0;
	//각각 노드에 이어진 노드 번호 저장
	for (int i = 0; i < edge.size(); i++) {
		Graph[edge[i][0]].push_back(edge[i][1]);
		Graph[edge[i][1]].push_back(edge[i][0]);
	}
	bfs();
	answer = getMax(n);
	return answer;
}