(프로그래머스 JS)가장 먼 노드

(프로그래머스 JS)가장 먼 노드

728x90

반응형

https://programmers.co.kr/learn/courses/30/lessons/49189?language=javascript

728x90

큐와 BFS를 이용한 문제 풀이.

우선 그래프를 그리기 위해 n + 1의 크기만큼 2차원 배열 graph를 선언.

노드의 방문 여부를 알기 위한 visited 배열을 선언.

for문.

주어진 edge는 무방향 그래프이기 때문에 두 노드에 해당하는 번호를 각각 넣어줘야 한다.

큐 class를 만들어 bfs를 위한 큐를 만든다.

문제가 1부터 가장 먼 노드를 찾아야 하기 때문에 큐에 1을 넣어 시작(visited[1]도 true로 바꾼다.)

BFS.

현재 큐에 담겨있는 사이즈가 answer가 될 수 있다.

왜냐하면 가장 끝까지 간 경우, 큐가 비기 때문에 현재 depth의 노드 개수가 큐의 현재 크기이기 때문이다.

큐의 size만큼 while문 실행.

현재 방문한 노드의 인접한 노드 중 방문하지 않은 노드는 큐에 넣어준다.

visited 또한 true로 설정.

(size만큼 실행하기 때문에 새로 추가된 노드는 다음 depth에서 방문한다.)

이 while문을 실행하면 자동으로 1에서 가장 먼 노드들의 개수를 구할 수 있다.

class Queue{ constructor(){ this.queue = []; this.front = 0; this.rear = 0; } push(value){ this.queue[this.rear++] = value; } pop(){ const value = this.queue[this.front]; delete this.queue[this.front++]; return value; } size(){ return this.rear - this.front; } } function solution(n, edge) { let answer = 0; const queue = new Queue(); const graph = Array.from(Array(n + 1), () => []); const visited = Array.from(Array(n + 1).fill(false)); for(const v of edge){ const e1 = v[0]; const e2 = v[1]; graph[e1].push(e2); graph[e2].push(e1); } queue.push(1); visited[1] = true; while(queue.size()){ let size = queue.size(); answer = size; while(size--){ const start = queue.pop(); for(let i = 0; i < graph[start].length; i++){ const target = graph[start][i]; if(!visited[target]){ queue.push(target); visited[target] = true; } } } } return answer; }

728x90

반응형

from http://eunchanee.tistory.com/535 by ccl(A) rewrite - 2021-08-04 19:01:03