Graph - DFS, BFS

문제
주어진 인접행렬에서 한 정점에서 다른 정점으로 이어지는 길이 존재하는지
입력
인자 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를 반환합니다.

BFS

길의 경로를 묻는 것이 아닌, 그저 길이 존재하는지의 유무를 반환하는 것으로
bfs가 적합하다.

//bfs method -> 현 정점과 직접 이어진 모든 정점을 돌고 그 다음 레벨로 감
function getDirections(matrix, from, to) {
  // 큐 구현 틀 만들기
  let Q = []
  let enQ = (vertex) => Q.push(vertex)
  let deQ = () => Q.shift()

  let isVisited = new Array(matrix.length).fill(false) 
  // 방문 여부를 boolean으로 명시하기 위한 배열 기본 설정.

  enQ(from); // 큐에 시작 정점을 넣어주고
  isVisited[from] = true; // 방문 여부 수정

  while (Q.length) { // 방문 예정인 정점 목록들이 빌 때까지 반복
    let now = deQ() // 현재 정점은 큐의 첫 번째 정점
    if (now === to) return true // 현재 정점이 목표지라면 트루!
    for (let next = 0; next < matrix[now].length; next++) {
    // 목표지가 아니라면 현 정점과 연결된 다른 정점을 물색한다.
      
      if (!isVisited[next] && matrix[now][next]) {
        enQ(next) 
        isVisited[next] = true;
      } // 현재 정점과 간선으로 이어져있고 방문한 적 없는 정점이라면
    } // 방문 예정 목록인 큐에 넣고 방문 여부를 수정한다.
  }
  return false;
}

조금 더 간결하게 작성한 버전

function getDirections(matrix, from, to) {

let Q = [from] // 큐는 방문할 예정인 정점들의 목록.
let isVisited = [from] // 중복 방문을 피하기 위해 방문한 정점을 명시한다.

while (Q.length) {
  let now = Q.shift() 
  if (now === to) return true 
  // 현 정점이 목표지점이면 도착한 것이다. 길이 있다!
  for (let next = 0; next < matrix[now].length; next++) {
    if (matrix[now][next] === 1 && !isVisited.includes(next)) {
      Q.push(next) 
      // 간선이 있는데 방문하지 않은 곳이라면! 방문예정 목록에 넣어준다.
      isVisited.push(next); // 그리고 방문했던 정점 목록에 추가한다.
    }
  }
}
return false;
}

DFS

// dfs 방식 -> 많은 간선 중에 하나에만 올인
function getDirections(matrix, from, to, 
	isvisited = new Array(matrix.length + 1).fill(false)) {
 // 방문 여부 배열을 미리 파라미터로 주자.
 
 const now = from // 현재 정점
 isvisited[now] = true; // 현재 정점 방문도장
  
 if (now === to) return true; // base case; 현재가 목적지라면 트루!

 // 현재 정점의 간선을 찾아라!
 for (let next = 0; next < matrix[now].length; next++) { 
   
   if (!isvisited[next] && matrix[now][next]) { 
   // 현재와 이어져있고 내가 가보지 않았다면 
     let recursion = getDirections(matrix, next, to, isvisited) 
     // 재귀로 동일한 일 반복.
     if (recursion) return true; 
     // 자식노드를 파고들다 목적지에 도착했다면 
     // 다른 길은 보지도 말고 트루로 돌아오라.
   }
 }
 return false;
}

중복 방문 체크는 그냥 정점 자체를 넣어주고
includes 메소드로 확인하는 것이 더 깔끔하다.

function getDirections(matrix, from, to, isVisited = []) {
  let now = from
  isVisited.push(now)

  if (now === to) return true;
  for (let next = 0; next < matrix[now].length; next++) {
    if (matrix[now][next] && !isVisited.includes(next)) {
      let recursion = getDirections(matrix, next, to, isVisited)
      if (recursion) return true;
    }
  }
  return false;
}

Ramne

💡

이전 포스트

React

다음 포스트

Graph - DFS, BFS

깊이 우선 탐색 Depth-First Search

너비 우선 탐색 Breadth-First Search

구현 방법

인접 행렬 길 찾기 문제

BFS

DFS

React

Graph - DFS, BFS 심화

0개의 댓글

관련 채용 정보