[프로그래머스] 가장 먼 노드 - javascript(풀이 있음)

👀문제

가장 먼 노드 - 3단계

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

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

문제 설명

n개의 노드가 있는 그래프가 있습니다. 각 노드는 1부터 n까지 번호가 적혀있습니다. 1번 노드에서 가장 멀리 떨어진 노드의 갯수를 구하려고 합니다. 가장 멀리 떨어진 노드란 최단경로로 이동했을 때 간선의 개수가 가장 많은 노드들을 의미합니다.

노드의 개수 n, 간선에 대한 정보가 담긴 2차원 배열 vertex가 매개변수로 주어질 때, 1번 노드로부터 가장 멀리 떨어진 노드가 몇 개인지를 return 하도록 solution 함수를 작성해주세요.

제한사항

• 노드의 개수 n은 2 이상 20,000 이하입니다.
• 간선은 양방향이며 총 1개 이상 50,000개 이하의 간선이 있습니다.
• vertex 배열 각 행 [a, b]는 a번 노드와 b번 노드 사이에 간선이 있다는 의미입니다.

입출력 예

nvertexreturn

6

[[3, 6], [4, 3], [3, 2], [1, 3], [1, 2], [2, 4], [5, 2]]

3

입출력 예 설명

예제의 그래프를 표현하면 아래 그림과 같고, 1번 노드에서 가장 멀리 떨어진 노드는 4,5,6번 노드입니다.

---

👀문제 풀이

BFS를 이용하면 쉽게 풀 수 있는 문제가 아닌가 싶습니다.

그래프 문제 중 가장 먼~ 가장 가까운~ 처럼 최단 최장 거리를 구할때는 BFS를 생각하시면 빠르게 답을 도출해 내실 수 있을 겁니다.

아래는 주석으로 설명을 달아 놓은 풀이와, 문제 답 둘다 남겨 놓겠습니다.

1) 풀이주석 포함 답

function solution(n, edge) {
    return bfs(1, edge, n);
}
const bfs = (start, arr, end) => {
	//  인자로 시작값, 탐색할 배열, 길이를 받는 BFS 함수를 만들어 줍니다.
 
    const visited = new Array(end + 1).fill(false);
    // 방문한 노드를 재방문 하는 일이 없도록 방문을 체크하는 배열을 만들고,
    // 초기에는 아무 노드도 방문 하지 않았으니 false로 초기화를 해줍니다.
    
    const level = new Array(end + 1).fill(0);
    //각 노드가 1과 어느정도 거리가 있는지를 담을 level이라는 배열을 만들어 주고,
    // 거리를 0으로 초기화를 해줍니다.
    
    const queue = [start];
    // queue에 start값을 넣어줍니다.
    
    visited[start] = true;
    // start를 방문체크 해줍니다.
    
    while (queue.length) {
    // queue가 빌때 까지 루프를 돌릴 겁니다. 큐가 비었다는 소리는 모든 노드를 다 탐색이 끝났다는 이야기 입니다.
    
        const head = queue.shift();
        // 선입선출이 특징인 queue의 자료구조 특징에 맞게 queue 에서 탐색을 시작할 기준이 될 노드를 꺼냅니다.
        
        const lev = level[head] + 1
        // 각 노드와 1과의 거리가 담겨 있는 level배열에 현재 기준으로 잡고 있는 head랑 연결되어 있는 노드들은
        // 1과의 head와의 거리 + 1 이므로 lev라는 변수에 level[head] + 1를 담아줍니다.
        
        for (let node of arr) {
        	이제 arr를 돌면서 각 노드 배열을 탐색할 겁니다.
            근데 정렬되어있지 않으므로 양방향으로 모두 탐색해 주어야 합니다.
            
            if (node[0] === head && !visited[node[1]]) {
            // ex) node = [2, 3], head = 2 이라면 2과 연결되어있는 노드를 아직 방문하지 않았을 경우
                queue.push(node[1]);
                // 큐에 탐색해야할 노드를 넣어주고
                visited[node[1]] = true;
                // 방문처리
                level[node[1]] = lev;
                // 거리 등록
            } else if (node[1] === head && !visited[node[0]]) {
             // ex) node = [3, 2], head = 2 이라면 2과 연결되어있는 노드를 아직 방문하지 않았을 경우
                queue.push(node[0]);
                // 큐에 탐색해야할 노드를 넣어주고
                visited[node[0]] = true;
                // 방문처리
                level[node[0]] = lev;
                // 거리 등록
            }
        }

    }
    const maxLevel = Math.max.apply(null, level);
    // 가장 먼거리
    return level.filter((i) => i === maxLevel).length;
    //가장 먼거리들만 남겨둔 배열의 길이 값을 리턴
}

 

2) 풀이주석 제외 답

function solution(n, edge) {
    return bfs(1, edge, n);
}
const bfs = (start, arr, end) => {
    const visited = new Array(end + 1).fill(false);
    const level = new Array(end + 1).fill(0);
    const queue = [start];
    visited[start] = true
    while (queue.length) {
        const head = queue.shift();
        const lev = level[head] + 1
        for (let node of arr) {
            if (node[0] === head && !visited[node[1]]) {
                queue.push(node[1]);
                visited[node[1]] = true;
                level[node[1]] = lev;
            } else if (node[1] === head && !visited[node[0]]) {
                queue.push(node[0]);
                visited[node[0]] = true;
                level[node[0]] = lev;
            }
        }

    }
    const maxLevel = Math.max.apply(null, level);
    return level.filter((i) => i === maxLevel).length;
}

---

👀 실행결과