알고리즘 2 : 인접 행렬 길찾기

인접 행렬 길 찾기

주어진 인접행렬에서 한 정점으로부터 다른 정점으로 이어지는 길이 존재하는지 true/false 로 반환한다.

 

인자 1 : matrix

 2차원 Array 

인자 2 : from

시작 정점, number 타입

인자 3 : to

도착 정점, number 타입

 

입출력 예시

• 정점 0에서 2로 가는 길이 존재하는지 확인한다.
• 0 --> 1 로 가는 간선이 존재하고, 1 --> 2 로 가는 간선이 존재하기 때문에 true를 반환한다.

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

 

코드

function getDirections(matrix, from, to) {

//한번 간 곳은 다시 가지 않는다. 지나온 곳을 true로 변경할 것임
  let visited = new Array(matrix.length).fill(false)
  
  let queue = []
  queue.push(from)//0에 시작, queue는 자료구조 도구임
  visited[from]=true//0번 정점을 지났다는 의미로 visited[0]=true 할당
  
  while(queue.length>0){
    current = queue.pop();//queue방식, 들어온 순서대로 내보낸다.queue=[]이 된다.
    //현재 위치에 0번 정점 할당
    if(current === to) return true// 현재위치가 to 정점이라면 true

    for(let i = 0;i<matrix[current].length;i++){//현재 정점0에서 갈 수 있는 루트를 검색. 1을 찾을 것임.
      if(matrix[current][i]===1 && visited[i]===false)//연결된 길인 동시에(1), 아직 지나지 않은 정점(false)라면 
      {
        visited[i]=true//방문하고 true로 바꿔준다.
        queue.push(i)//queue에 현재위치 할당.
      }
    }
  }
  return false//위의 모든 과정에서 아무일이 없었다면 길이 없다는 뜻임 false


}

 

상세설명

1. 먼저 이것부터 알아야 한다. 예외는 있지만 대부분의 경우에 통하는 방법이다.

 

• Matrix : 연결관계를 확인하는 문제, 2차원배열 사용한다. (인덱스 만으로 조회를 쉽게 할 수 있으니깐)

다음과 같은 상황에서는 From이 vertex(정점), To가 edge(간선) 이라 생각하고 문제를 풀면 편함

• List : vertex를 추가하거나 삭제하는 문제, 객체 사용. ( 배열은 추가 삭제할때마다 인덱스가 당겨지거나 밀려서 관리하기가 복잡해지지만 객체는 고정되 있기 때문에 관리가 편하다.)

 

Queue 사용 (BFS) :

• while(queue.length>0) : queue의 탈출조건은 남아있는 것이 없을때임
• 한번간곳은 다시 가지 않는다 : [false,false,false,...,false]배열 만들고 체크할때 마다 true로 바꿔준다.

 // 방문했다는 것을 표시하기 위해 1차원 행렬을 생성합니다.
  const isVisited = new Array(matrix.length).fill(false);

  // 첫 정점 방문 여부를 표시합니다.
  isVisited[from] = true

  // queue(방문할 곳)의 사이즈가 0이 될 때까지 반복합니다.
  while (queue.length > 0) {

Stack 사용 (DFS) :

• 반복문 쓰고 싶을때 재귀함수 사용

2. 지나온 곳을 체크할 visited 배열 선언

한번 지나온 곳은 다시 지나가지 않을 것임.

let visited = new Array(matrix.length).fill(false)

 

3. queue 선언, 출발지점 설정

 

  let queue = []
  queue.push(from)//queue=[0]
  visited[from]=true//[t,f,f,f]

 

4. 반복문. queue의 탈출조건은 queue 안에 아무것도 없을 때 이다.

• 반복문은 현재위치 current정점(matrix[current]) 에서 길을 찾는 작업이다.(1이면서 visited에 true로 할당되지 않은 인덱스)
• 그런 값이 있다면 그 값으로 이동했다고 표시한다.(visited[i]=true)
• while문을 또 돌리기 위해 queue에 값을 할당한다.(queue의 탈출조건은 queue.length=0일때임)
• 위에서 이동했을 경우에는 다시 while문의 처음으로 올라가 queue.pop()을 현재위치 current에 할당한다.

만약 반복문을 다 지나도록 아무일이 없었다면 연결된 곳이 없다는 뜻이다. false를 리턴한다.

while(queue.length>0){
    //현재위치, queue는 선입선출임
    let current = queue.pop();//queue=[],current = 0
    //만약 현재위치가 목적지라면 true 리턴
    if(current === to) return true

    for(let i = 0;i<matrix[current].length;i++){
      if(matrix[current][i]===1 && visited[i]===false)
      {
        visited[i]=true//[t,t,f,f], 지나왔다는 표시
        queue.push(i)//queue = [1] while을 끝내지 않기 위해 queue에 할당
      }
    }
    
}
  return false//아무길도 없음
  
  }