문제
설명
The number of nodes n and a two-dimensional array with edges is given as a parameter.
Please write a function that returns how many nodes are farthest from node 1.
The furthest node is the node with the largest number of edges when moving to the shortest path.
매개변수
- n : number type으로 number of nodes를 나타냄 (n >= 2)
- edge : Two-Dimensional Array which Indicates the edge of each node (bidirectional)
아웃풋
number type 리턴하기
입출력 예시
let edge = [[4,1],[3,4],[1,2],[2,3],[2,5],[5,3]]
let output = test1(5,edge);
console.log(output); // --> 2
Solution
BFS와 queue를 사용하여 Edge를 따라 1부터 모든 Node 방문하기
Node에 대한 중복 방문을 막으면 최단거리를 구할 수 있음
각 Node에 대한 방문 여부와 1에서 거리를 담을 배열 isVisited와 distanceArr 선언 (인덱스 === 노드 번호)
function test(n, edge) {
// 아래에서 제작한 bfs 함수 사용
return bfs(1, n, edge)
}
// bfs 함수 제작
function bfs (start, end, array) {
const isVisited = Array(end+1).fill(false);
const distanceArr = Array(end+1).fill(0);
// queue에 start(1번 노드)를 할당하고, 방문 기록을 true로 변경
let queue = [start];
isVisited[start] = true;
while (queue.length>0) {
// queue의 0번째 인덱스를 꺼내 head 변수에 할당
// 1에서 head까지의 거리에 추가로 1을 더한 뒤 distance 변수에 할당
let head = queue.shift()
let distance = distanceArr[head] +1;
for (let node of array) {
// head와 edge로 연결된 노드를 아직 방문하지 않았을 경우, 해당 노드를 방문하고 거리 입력
if (node[0] === head && !isVisited[node[1]]) {
queue.push(node[1])
isVisited[node[1]] = true;
distanceArr[node[1]] = distance;
} else if (node[1] === head && !isVisited[node[0]]) {
queue.push(node[0])
isVisited[node[0]] = true;
distanceArr[node[0]] = distance;
}
}
}
// 1에서 거리가 최대인 노드의 개수를 리턴
let maxDistance = Math.max(...distanceArr)
let maxArr = distanceArr.filter(el => el === maxDistance)
return maxArr.length
}
반응형
'프로그래밍 > 알고리즘, 프로그래밍 언어' 카테고리의 다른 글
[코딩테스트] sumOfSubOrdinates - DFS (JavaScript) (0) | 2022.02.07 |
---|---|
[코딩테스트] 나선형 순회 spiralTraversal (JavaScript) (0) | 2022.02.07 |
[코딩테스트] identical characters (JavaScript) (0) | 2022.02.03 |
[코딩테스트] rowBikesOut (JavaScript) (0) | 2022.02.03 |
[코딩테스트] Codility 6-2 MaxProductOfThree (JavaScript) (0) | 2022.01.29 |
댓글