[프로그래머스/그래프, BFS] lv3. 가장 먼 노드 (JavaScript)

gitgitWi's TIL·2021년 2월 6일
0

1번 노드에서 각 노드로 최단 경로로 이동했을 때
간선을 가장 많이 거치는 노드의 수?

  • 모든 간선 길이는 1이고 최단 거리를 구하는 문제이기 때문에, BFS로 해결
  • 재귀로 풀었다가 런타임 에러, 시간 초과 나서 iteration(while)으로 해결
  • 노드 수 최대 2만/간선 수 최대 5만이기 때문에, 최신 브라우저 JS엔진 최대 콜 스택 사이즈가 10만 내외인걸 고려해 while로 풀 생각을 했어야 했다..
/**
 * @param {number} n 노드 개수 2~20,000
 * @param {number[]} edge 간선 정보, 1~50,000
 * @returns {number} 가장 멀리 떨어진 노드 갯수
 */
const solution = (n, edge) => {
	const START = 1;
	const results = Array(n + 1).fill(Number.MAX_SAFE_INTEGER);
	results[START] = 0;

	const graph = edge.reduce((acc, val) => {
		const [a, b] = val;
		acc[a] ? acc[a].push(b) : (acc[a] = [b]);
		acc[b] ? acc[b].push(a) : (acc[b] = [a]);
		return acc;
	}, {});

	const visited = Array(n + 1).fill();
	visited[START] = true;

	const queue = [{ node: START, count: 0 }];
	let maxi = 0;

	while (queue.length) {
		const { node, count } = queue.shift();
		results[node] = count;
		if (maxi < count) maxi = count;

		for (const nextNode of graph[node]) {
			if (visited[nextNode]) continue;
			queue.push({ node: nextNode, count: count + 1 });
			// 여기서 다음 노드에 대해 미리 방문 처리해주어서 중복 방문 제거
			// 모든 간선 길이가 1이기 때문에 가능한 듯?
			visited[nextNode] = true;
		}
	}

	return results.filter((e) => e === maxi).length;
};

profile
가볍게 TIL 남기는 velog, 꾸준히 성장하는 개발자

0개의 댓글