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

링크

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

코딩테스트 연습 - 가장 먼 노드 | 프로그래머스

풀이

간단한 BFS로 풀 수 있다.

 

일단 양방향 그래프를 만든 후

출발지에서 도착한 위치와 거리를 저장할수 있는 구조체를 만들었다.

이전 노드에서 다음 노드에 도착 하였을때 거리를 1 증가 시켜 주었고

방문 여부를 확인하기 위해서 visited배열을 모두 -1로 초기화 하고

방문한 위치를 기억 하기 위해 visited을 거리만큼 갱신 했고

가장 큰 거리와 visited배열과 비교하여 거장 먼 노드의 갯수를 찾을수 있었다.

#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
#include<string>
#include<set>
#include<map>
#include<cstring>
#include<functional>

#define INF 2e9
#define SIZE 20010

using namespace std;

typedef long long int ll;

typedef struct Data {
	int n, cost=0;
}Data;

vector<int> arr[SIZE];
int visited[SIZE];
queue<Data> q;

int solution(int n, vector<vector<int>> edge) {
	int e_size = edge.size();

	for (int i = 0; i < e_size; i++) {
		arr[edge[i][0]].push_back(edge[i][1]);
		arr[edge[i][1]].push_back(edge[i][0]);
	}

	memset(visited, -1, sizeof(visited));

	Data start;
	start.n = 1;
	q.push(start);

	int m_len = 0;
	while (!q.empty()) {
		Data here = q.front();
		q.pop();

		visited[here.n] = visited[here.n] == -1 ? 0 : visited[here.n];
		m_len = max(m_len, visited[here.n]);

		for (auto next : arr[here.n]) {
			if (visited[next] != -1)
				continue;

			Data nxt; nxt.n = next; nxt.cost = here.cost + 1;
			visited[next] = nxt.cost;
			q.push(nxt);
		}
	}

	int res = 0;
	for (int i = 0; i < n; i++) {
		res += m_len == visited[i] ? 1 : 0;
	}

	return res;
}