프로그래머스 가장 먼 노드

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

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

#include<stdio.h>
#include<iostream>
#include <string>
#include <vector>
#include <queue>
using namespace std;
#define N_SIZE 20001
struct Data {
	int num, cnt;
};
int solution(int n, vector<vector<int>> edge) {
	int answer = 0;
	vector<int>G[N_SIZE];

	for (int i = 0; i < edge.size(); i++) {
		//양방향
		G[edge[i][0]].push_back(edge[i][1]);
		G[edge[i][1]].push_back(edge[i][0]);
	}
	queue<Data>q;
	int visit[N_SIZE] = { 0, };
	q.push({ 1,1 });
	visit[1] = 1;
	int cnt = 0;
	while (!q.empty()) {
		Data c = q.front(); q.pop();
		for (int i = 0; i < G[c.num].size(); i++) {
			Data n;
			n.num = G[c.num][i]; n.cnt = c.cnt + 1;
			if (visit[n.num] == 0) {
				visit[n.num] = n.cnt;
				cnt = n.cnt;
				q.push(n);
			}
		}
	}
	for (int i = 1; i <= N_SIZE; i++) {
		if (visit[i] == cnt)answer++;
	}

	return answer;
}
int main(void) {
	cout << solution(6, { {3, 6}, {4, 3}, {3, 2}, {1, 3}, {1, 2}, {2, 4}, {5, 2} });

	return 0;
}

그래프를 구현할 줄 안다면 쉬운 문제 입니다. 그리고 노드를 탐색하는 방식을 하는법만 알고 있다면 쉽게 구할 수 있습니다. 가장 기본적으로 그래프를 구현하고 체크하는 방식으로 문제를 풀이했습니다. 참고해주세요.