인접 행렬 길찾기

function getDirections(matrix, from, to) {
  const queue = [from]; // 큐를 초기화하고 시작 정점을 삽입
  const visited = new Array(matrix.lengt).fill(false); // 방문 여부를 저장할 배열

  while (queue.length > 0) {
    const node = queue.shift(); // 큐에서 노드를 추출
    if (node === to) return true; // 목적지에 도착하면 true 반환

    visited[node] = true; // 방문한 노드는 visited 배열에 표시

    for (let i = 0; i < matrix[node].length; i++) {
      if (matrix[node][i] && !visited[i]) { // 인접한 노드 중 방문하지 않은 노드가 있으면 큐에 추가
        queue.push(i);
      }
    }
  }

  return false; // 도착하지 못한 경우 false 반환
}

ex)

[
		[0, 1, 0, 0],
		[0, 0, 1, 0],
		[0, 0, 0, 1],
		[0, 1, 0, 0],
	],
	0,
	2
);

큐에 출발 지점 0을 삽입

visited= [false , false , false , false ] 생성

 

큐에서 0을 추출하고 , visited = [ true , false , false , false ]  로 변경

matrix[0][1]는 1이고 방문하지 않아서 

queue에 추가하여 [1]이 된다.

 

큐에서 1을 추출하고 , visited = [true , true , false, false]로 변경

matrix[1][3]는 1이고 visited[3]는 false로 방문하지 않아서

queue에 추가하여 [3]이 된다.

 

큐에서 3을 추출하고 , visited = [true , true ,false , true]로 변경

matrix[3][1] , matrix[3][2]는1이고 visited[2]는 false로 방문하지 않아서 

queue에 추가하여 [2]가 된다.

목적지에 도착해서 true로 반환된다.