[DFS] 경로 탐색

🚩 경로 탐색 (인접행렬, 인접리스트)

 

📖 문제 설명 : 방향그래프가 주어지면 1번 정점에서 N번 정점으로 가는 모든 경로의 가지 수를 출력

(인접 행렬, 인접 리스트)

 

인접 행렬 방식

// 경로 탐색(인접행렬)

let path = [] // 탐색한 노드 경로

function DFS(n, graph, visited, v, arr) {
  if (v === n) {
    // 누적 경로 + 현재 경로
    path.push([...arr, v])
    return
  }

  visited[v] = 1 // 방문 처리

  // 인접 행렬을 순회하면서 방문하지 않은 노드들의 경로를 재귀적으로 탐색
  for (let j = 1; j <= n; j++) {
    if (graph[v][j] === 1 && visited[j] === 0) {
      DFS(n, graph, visited, j, [...arr, v])
      visited[v] = 0 // 방문 해체
    }
  }
}

function solution(n, node) {
  let answer = 0
  let graph = Array.from(Array(n + 1), () => Array(n + 1).fill(0))
  let visited = Array.from(Array(n + 1), () => 0) // 방문 처리

  for (let [x, y] of node) {
    graph[x][y] = 1
  }

  DFS(n, graph, visited, 1, [])

  console.log(path)
  answer = path.length
  return answer
}

let node = [
  [1, 2],
  [1, 3],
  [1, 4],
  [2, 1],
  [2, 3],
  [2, 5],
  [3, 4],
  [4, 2],
  [4, 5],
]
console.log(solution(5, node))

 

인접 리스트 방식

// 경로 탐색(인접리스트)

let path = [] // 탐색한 노드 경로

function DFS(n, graph, visited, v, arr) {
  if (v === n) {
    // 누적 경로 + 현재 경로
    path.push([...arr, v])
  }
  visited[v] = 1 // 현재 노드 방문 표시

  // 현재 노드의 배열 길이까지 탐색
  for (let j = 0; j < graph[v].length; j++) {
    // 현재 노드 값에 해당하는 방문 배열이 방문 한 적 없을 때
    if (visited[graph[v][j]] === 0) {
      DFS(n, graph, visited, graph[v][j], [...arr, v])
      visited[graph[v][j]] = 0 // 방문 해제
    }
  }
}

function solution(n, node) {
  let answer = 0
  let graph = Array.from(Array(n + 1), () => Array(0))
  let visited = Array.from(Array(n + 1), () => 0) // 방문 처리

  for (let [x, y] of node) {
    graph[x].push(y)
  }

  DFS(n, graph, visited, 1, [])

  console.log(path)
  answer = path.length
  return answer
}

let node = [
  [1, 2],
  [1, 3],
  [1, 4],
  [2, 1],
  [2, 3],
  [2, 5],
  [3, 4],
  [4, 2],
  [4, 5],
]
console.log(solution(5, node))

 

👨‍💻 코드 설명

인접 행렬은 구현이 쉽지만, 노드의 개수만큼 배열을 할당해야 하므로 메모리에 큰 낭비가 된다.
인접 리스트는 구현이 행렬에 비해 다소 어렵지만, 주어진 연결 노드만을 가지고 있기 때문에
메모리에서 큰 장점을 가진다.

 

잘못된 설명, 코드, 예외 케이스가 있다면 댓글 남겨주시면 수정하겠습니다.