S4) Unit 1. [실습] Tree & Graph 문제

📣  인접 행렬 길찾기

Q. 주어진 인접행렬에서 한 정점으로부터 다른 정점으로 이어지는 길이 존재하는지 반환해야 합니다.

function getDirections(matrix, from, to) {
  // TODO: 여기에 코드를 작성합니다.
  if(matrix[from][to] === 1) return true;

  const queue = [];
  queue.push(from);
  const isVisited = new Array(matrix.length).fill(false);
  isVisited[from] = true;
  //console.log(matrix[0].length);
  console.log(isVisited);

  while(queue.length > 0){
    let pop = queue.shift();
    if(pop === to) return true;
    // 내가 큐에서 뺀 정점이 도착지점이라면 true 반환
    for(let i=0; i<matrix[pop].length; i++){
      // 큐에서 뺀 정점의 간선 확인
      if(matrix[pop][i] && isVisited[i] === false){
        // 간선이 있고, 해당 정점 지나간 적 없으면
        queue.unshift(i);
        // 다음에 가기 위해서 큐에 저장
        isVisited[i] = true;
      }
    }
  }
  return false;
  // 다 돌았는데도 찾는 정점에 도달하지 못했다면 false 반환
}

 

---

📣  연결된 정점들

 

Q. 방향이 없는 간선들의 목록이 주어질 때, 연결된 정점의 컴포넌트(그룹들)가 몇 개인지 반환하는 함수를 작성하세요.

function connectedVertices(edges) {
  // TODO: 여기에 코드를 작성합니다.
  const max = Math.max(...edges.flat());
  // flat() => 모든 배열을 이어붙인 새로운 배열 반환
  const matrix = new Array(max + 1).fill(0).map(item => new Array(max + 1).fill(0));
  // 인접 행렬 만들어주기
  let isvisited = new Array(matrix.length).fill(false);
  // 방문한 적 있는지 저장할 배열

  for(let i=0; i<edges.length; i++){
  // 만들어 둔 인접행렬에 인자로 받은 배열 돌면서 인접행렬 완성해주기
    matrix[edges[i][0]][edges[i][1]] = 1;
    matrix[edges[i][1]][edges[i][0]] = 1;
  }

  let count = 0;
  //i번째 정점을 지나간 적이 없다면 bfs를 실행
    for (let i = 0; i < matrix.length; i++) {
      if (!isvisited[i]) {
      // 방문한 적이 없다면
        bfs(matrix, i, isvisited);
        // bfs로 실행해준다.
        count++;
      }
    }
    return count;
}

function bfs(matrix, from, isvisited) {
// 모든 정점 돌면서 확인
  let queue = [from];
  // 시작할 정점 queue에 넣어주고
  isvisited[from] = true;
  // queue에 넣어준 정점은 방문 한거니까 방문 배열 true로 바꿔주기
  while (queue.length > 0) {
    let pop = queue.pop();
    // 큐에서 하나씩 빼면서
    for (let i = 0; i < matrix[pop].length; i++) {
    // 지금 있는 정점에서 모든 정점을 돌면서
      if (matrix[pop][i] === 1 && !isvisited[i]) {
      // 지금 있는 정점에서 인접한 정점 찾고, 그 정점을 방문한 적이 없다면
        queue.unshift(i);
        // 큐의 맨 앞에 그 정점을 넣어주고
        isvisited[i] = true;
      	// 그 정점 방문했다고 표시해주기
      }
    }
  }
}