TIL day5-1 bfs,dfs, 프로그래머스 가장 먼 노드 풀이

그래프 탐색에는 두 가지가 있다.

DFS(깊이 우선 탐색)

dfs에 대해서 먼저 알아보자.

탐색 알고리즘

a->b->c->d 순으로 탐색

코드:

  // 현재 노드 방문
  visited[v] = true;
  // 방문 노드 출력
  console.log(v);

  // 인접 노드 탐색
  graph[v].forEach(i => {
    // 방문하지 않았다면
    if (!visited[i]) {
      // 재귀 호출
      dfs(graph, i, visited);
    }
  })
}

// 노드 연결 정보
const graph = [
  [],
  [2, 3, 8],
  [1, 7],
  [1, 4, 5],
  [3, 5],
  [3, 4],
  [7],
  [2, 6, 8],
  [1, 7]
];

// 방문 정보
const visited = new Array(graph.length).fill(false);

// 호출
dfs(graph, 1, visited);

BFS(깊이 우선 탐색)

탐색

코드

function bfs(graph, v, visited) {
  // 큐 구현
  const queue = [v];
  // 현재 노드 방문
  visited[v] = true;

  // 큐가 빌 때까지 반복
  while (queue.length !== 0) {
    // 큐에서 원소 한 개 뽑아옴
    const node = queue.shift();
    // 방문
    console.log(node);
    
    // 원소의 인접 노드 탐색
    graph[node].forEach(i => {
      // 방문한 적이 없다면
      if (!visited[i]) {
        // 큐에 추가
        queue.push(i);
        // 방문 처리
        visited[i] = true;
      }
    })
  }
}

// 노드 연결 정보
const graph = [
  [],
  [2, 3, 8],
  [1, 7],
  [1, 4, 5],
  [3, 5],
  [3, 4],
  [7],
  [2, 6, 8],
  [1, 7]
];

// 방문 정보
const visited = new Array(graph.length).fill(false);

// 호출
bfs(graph, 1, visited);

프로그래머스 가장 먼 노드 문제풀이:

문제:

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

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

풀이:

가장 '먼' 노드의 갯수를 구하는 문제여서, 깊이우선 탐색을 생각 하면, 탐색하는데 큰 조건이 필요치 않아 쉽게 해결 할 수 있을 것이다.

입출력 예

n=6
vertex [[3, 6], [4, 3], [3, 2], [1, 3], [1, 2], [2, 4], [5, 2]]

return값 3
입출력 예 설명
1번 노드에서 가장 멀리 떨어진 노드는 4,5,6번 노드다.

코드:

function solution(n,vertex){
    return bfs(1,vertex,n);
}

const bfs=(start,arr,end)=>{
    const visited =new Array(end+1).fill(false);
    const lenn = new Array(end+1).fill(0);
    const queue = [start];
    visited[start]=true;
    while (queue.length){
        const head = queue.shift();//검사 숫자 1이면 1이 있는 요소를 탐색
        //console.log('head:',head);
        const len = lenn[head]+1;//길이 ex)1,2 2,3면 1->2은 길이가 1,  
        //1->3는 길이가 2
        console.log('lenn:',len);
        for (let i of arr){
            console.log(i);
            if(i[0]===head&& !visited[i[1]]){//검사하려는 숫자가 앞쪽에 있다면
                //console.log(i[1]);
                queue.push(i[1]);//뒷 숫자를 푸시
                visited[i[1]] =true;//방문한 노드 기록
                //console.log(visited[i[1]]);
                lenn[i[1]]=len;//방문한 노드의 길이 1 추가
                //console.log(lenn[i[1]]);
            }
            else if(i[1]===head && !visited[i[0]]){
                queue.push(i[0]);
                //console.log([i[1]]);
                visited[i[0]]=true;
                //console.log(visited[i[1]]);
                lenn[i[0]]=len;
                //console.log(lenn[i[0]]);
            }
            //console.log('큐:',queue);

        }

    }
    //console.log(lenn);
    const max=Math.max.apply(null,lenn);
    //console.log(max);
    return lenn.filter((i=> i === max)).length;

}

n=6;
vertex=[[3, 6], [4, 3], [3, 2], [1, 3], [1, 2], [2, 4], [5, 2]]
console.log(solution(n,vertex));

느낀점

dfs,bfs를 학업기간에도 배우며 힘들었던 기억이 있어 두려움이 있었으나 훌륭한 강의력에 곧바로 이해 할 수 있었다. 코드를 하면서 아쉬운 것은
shift()함수를 쓰지 않는 것이 좋다고 하여 queue를 직접 구현해서 써야 겠다고 끝나고 나서 알았다. 다시한번 queue를 구현해서 짜봐야겠다..
언제...?