[Graph] 인접 행렬 길찾기

문제

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

입력

• 인자 1: matrix
  Array 타입을 요소로 갖는 인접 행렬이 담긴 2차원 배열
• 인자 2: from
  Number 타입의 시작 정점
• 인자 3: to
  Number 타입의 도착 정점
• 출력
  boolean 타입을 리턴해야 합니다.

입출력 예시

const result = getDirections(
	[
		[0, 1, 0, 0],
		[0, 0, 1, 0],
		[0, 0, 0, 1],
		[0, 1, 0, 0],
	],
	0,
	2
);
console.log(result); // true
정점 0에서 2로 가는 길이 존재하는지 확인합니다.
0 --> 1 로 가는 간선이 존재하고, 1 --> 2 로 가는 간선이 존재하기 때문에 true를 반환합니다.

---

Solution

function getDirections(matrix, from, to) {
  // queue 안에 탐색할 정점들을 넣어주는 것, 이미 탐색한 정점은 제거해 주고, 탐색표시를 남길 것
  let queue = [from];
  let enqueue = (n) => queue.push(n);
  let dequeue = () => queue.shift();

  // 탐색한 정점에 표시를 남기기 위해 만들어진 변수, 탐색 완료된 정점은 true로 바꿔줌
  let isVisted = Array(matrix.length).fill(false);  // [false, false, false, false]
  isVisted[from] = true;

  // 더 이상 탐색할 정점이 없어질 때까지 반복함
  while(queue.length > 0) {
    let now = dequeue();  // 탐색해야 할 정점들이 있는 queue에서 우선순위에 있는 정점을 먼저 탐색할 준비
    if(now === to) return true; // 가장 우선순위에 있던 정점이 to(목적지)와 같을 때, true를 리턴하며 함수 종료

    for(let next = 0; next < matrix[now].length; next++) { // queue에 다음 탐색할 정점을 넣어주기 위한 반복문
      if(matrix[now][next] && (isVisted[next] === false)) {  // matrix[now][next] = 1(간선이 있고), 탐색하기 전이라면(false 라면)
        enqueue(next);  // queue에 next를 추가하여 다음에 탐색하도록 하고,
        isVisted[next] = true;  // 탐색했다는 표시로 true를 넣음
      }
    }
  }
  return false; // queue.length가 없다면 false를 반환
}