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

문제 설명

n개의 노드가 있는 그래프가 있습니다. 각 노드는 1부터 n까지 번호가 적혀있습니다. 1번 노드에서 가장 멀리 떨어진 노드의 갯수를 구하려고 합니다. 가장 멀리 떨어진 노드란 최단경로로 이동했을 때 간선의 개수가 가장 많은 노드들을 의미합니다.

노드의 개수 n, 간선에 대한 정보가 담긴 2차원 배열 vertex가 매개변수로 주어질 때, 1번 노드로부터 가장 멀리 떨어진 노드가 몇 개인지를 return 하도록 solution 함수를 작성해주세요.

제한사항

• 노드의 개수 n은 2 이상 20,000 이하입니다.
• 간선은 양방향이며 총 1개 이상 50,000개 이하의 간선이 있습니다.
• vertex 배열 각 행 [a, b]는 a번 노드와 b번 노드 사이에 간선이 있다는 의미입니다.

입출력 예

nvertexreturn

6

[[3, 6], [4, 3], [3, 2], [1, 3], [1, 2], [2, 4], [5, 2]]

3

입출력 예 설명

예제의 그래프를 표현하면 아래 그림과 같고, 1번 노드에서 가장 멀리 떨어진 노드는 4,5,6번 노드입니다.

---

문제가 가장 먼 노드라서 트리에서 가장 긴 거리에 있는 두 점을 고르는 문제인 줄 알았는데,

단순히 1에서 가장 먼 노드의 수를 구하는 문제였다.

 

그래프에서 모든 점을 방문하기에 dfs, bfs보다 좋은 방식은 없다.

이 문제는 특히 bfs를 풀면 쉬운 문제인데, 괜히 바보같이 dfs로 풀어서 반복되는 코드가 생겼다.

 

우선 사전작업으로 edge벡터에 있는 모든 정보를 그래프화한다.

v[a] : 점 a와 연결된 노드들이 저장되는 벡터이다. 

그래서 v[1]에 연결된 2, 3을 방문하고 2, 3에서 또 다른 점을 방문하는 식으로 최단 거리를 구한다.

 

dfs 과정은 어렵지 않다. 더 짧은 거리로 방문한 노드는 지나치고 아니라면 방문해서, 방문한 노드에서 또 연결된 다음 노드를 탐색하는 식이다. 

dfs 과정이 끝이 나면, 1로부터 최단거리를 저장한 visit 배열을 모두 탐색하며 최장거리를 잰다.

그 후엔 최장거리와 같은 노드의 수를 세서 반환하면 끝이다.

 

코드 원본 : https://github.com/chosh95/STUDY/blob/master/Programmers/%EA%B0%80%EC%9E%A5%20%EB%A8%BC%20%EB%85%B8%EB%93%9C.cpp

chosh95/STUDY

C++ 코드

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
vector<int> v[20001];
int visit[20001];
int maxLen;

void dfs(int idx, int dist) {
	if (visit[idx] > dist) visit[idx] = dist;
	else if (visit[idx] != 0) return;
	visit[idx] = dist;

	for (int i = 0; i < v[idx].size(); i++) 
		dfs(v[idx][i], dist + 1);
}

int solution(int n, vector<vector<int>> edge) {
	int answer = 0;
	for (int i = 0; i < edge.size(); i++) {
		int a = edge[i][0];
		int b = edge[i][1];
		v[a].push_back(b);
		v[b].push_back(a);
	}
	maxLen = 0;
	dfs(1, 1);

	for (int i = 1; i <= n; i++)
		if (maxLen < visit[i])
			maxLen = visit[i];

	for (int i = 1; i <= n; i++)
		if (visit[i] == maxLen)
			answer++;
	return answer;
}

int main()
{
	cout << solution(6, { {3,6},{4,3},{3,2},{1,3},{1,2},{2,4},{5,2} });
	for (int i = 1; i <= 6; i++) {
		cout << visit[i] << " ";
	}
	cout << maxLen;
}