[Javascript 코테 대비] 깊이 우선 탐색: DFS

DFS: Depth-First Search

깊이 우선 탐색이라고도 부르며, 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘이다.

function dfs(graph, v, visited) {
  // 현재 노드를 방문 처리한다
  visited[v] = true;
  print(v + '');
  
  // 현재 노드와 연결된 다른 노드를 재귀적으로 방문
  for const i in graph[v] {
  	if(!visited[i]) {
      dfs(graph, i, visited);
    }
  }
}
  
  // 각 노드가 연결된 정보를 리스트 자료형으로 표현(2차원 리스트)
const graph = [
  [],
  [2, 3, 8],
  [1, 7],
  [1, 4, 5],
  [3, 5],
  [3, 4],
  [7],
  [2, 6, 8],
  [1, 7]
];

const visited = [];
for (const i = 0; i < graph.length; i++) visited[i] = false;

dfs(graph, 1, visited)

실제 문제 풀이 시

2차원 배열에서 인접 영역 탐색하기

function dfs(data, i, j) {
  	// trival case
	if (i < 0 || j < 0 || i >= N || j >= M || data[i][j]) return 0;
  
  	data[i][j] = true;
  
  	dfs(board, i - 1, j);
    dfs(board, i, j - 1);
    dfs(board, i + 1, j);
    dfs(board, i, j + 1);
}