[알고리즘/javascript][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를 반환합니다.

const result2 = getDirections(
	[
		[0, 1, 0, 0, 0],
		[0, 0, 0, 1, 0],
		[0, 1, 0, 0, 0],
		[0, 1, 1, 0, 0],
		[1, 1, 1, 1, 0],
	],
	1,
	4
);
console.log(result2); // false

// 정점 1에서 4로 가는 길이 존재하는지 확인합니다.
// 1 --> 3,
// 3 --> 1 (정점 1을 다녀왔으니 다시 돌아가지 않습니다),
// 3 --> 2,
// 2 --> 1 (정점 1을 다녀왔으니 다시 돌아가지 않습니다)
// ...으로, 4에 도달할 수 없습니다.

 

코드

function getDirections(matrix, from, to) {
  // TODO: 여기에 코드를 작성합니다.
	// 1. 한번 방문한 정점을 다시 방문할 일이 없어야하기 때문에 방문 여부를 체크하기 위해 정점의 총 갯수만큼 1차원 배열을 만든다.
	// => 방문한 정점은 true, 방문하지 않은 정점은 false 값을 가지도록 한다.
	// 2. 큐를 만들어 방문할 정점은 넣고 방문하였다면 빼준다.
	// 3. from을 시작으로 from에서 간선이 있는 정점들을 차례대로 방문하여 to까지 이어지는 길이 있으면 true, 없으면 false를 반환한다.
	// => 방문할 정점을 queue에 넣고 queue에 있는 정점과 간선을 가지고 있는 정점들 중 방문하지 않은 곳이 있다면 queue에 넣고 방문한다.
	// => 만약 queue에 들어온 정점이 to와 같다면 true를 리턴한다.
	// => queue에 있는 정점과 간선을 가지고 있는 정점이 없거나, 있어도 이미 이전에 그 정점을 방문했었다면 길이 없다는 뜻이므로 
	// queue에 들어갈 다음 정점이 없어지게 되고, queue의 길이가 0이되므로 while문이 종료되고 false를 리턴한다.
	let visit = new Array(matrix.length).fill(false);
	let queue = [from];
	visit[from] = true;

	while(queue.length > 0){
		let current = queue.shift();
		if (current === to) return true;

		for(let i=0;i<matrix.length;i++){
			if(matrix[current][i] === 1 && !visit[i]){
				queue.push(i);
				visit[i] = true;
			}
		}
	}

	return false;
}