[Javascript로 정리하는 이코테] 4. DFS/BFS

http://www.yes24.com/Product/Goods/91433923

이것이 취업을 위한 코딩 테스트다 with 파이썬 - YES24

 

그래프의 기본 구조

• 그래프는 노드(정점)와 간선으로 표현된다.
• 그래프 표현 방식
  • 인접 행렬(Adjacency Matrix): 2차원 배열로 연결 관계 표현
  • 인접 리스트(Adjacency List): 연결 리스트로 연결 관계 표현

 

5-6. 인접 행렬 방식 예제

• 자바스크립트에서 무한대 숫자를 의미하는 Infinity를 이용해 연결되어 있지 않은 노드를 표현한다.

const INF = Infinity;

const graph = [
  [0, 7, 5],
  [7, 0, INF],
  [5, INF, 0]
];

console.log(graph);

 

5-7. 인접 리스트 방식 예제

• 자바스크립트로 인접 리스트를 표현하고자 할 때에도 2차원 배열을 이용하면 된다.

const graph = Array.from(Array(3), () => []);

//[노드, 거리] 형식으로 저장
graph[0].push([1, 7]);
graph[0].push([2, 5]);

graph[1].push([0, 7]);

graph[2].push([0, 5]);

console.log(graph);

//or
const graph = [
  [[1, 7], [2, 5]],
  [[0, 7]],
  [[0, 5]]
];

 

• 객체를 이용해도 된다. 노드의 값이 숫자가 아닌 경우 유용하게 쓸 수 있다.
• 사실상 자바스크립트의 배열은 내부적으로 객체이기 때문에, 아래의 첫 번째 예시는 위의 배열 예시와 동일하다.

const graph = {
  0: [[1, 7], [2, 5]],
  1: [[0, 7]],
  2: [[0, 5]]
};

const graph = {
  "A": ["B", "C"],
  "B": ["A"],
  "C": ["A"]
};

 

참고) 인접 행렬 vs. 인접 리스트

자세한 내용은 여기 참고 → https://gyyeom.tistory.com/67

 

 

DFS (Depth-First Search)

• 깊이 우선 탐색, 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘
• 스택 이용 → 재귀 함수 활용
• 탐색 수행 시 O(n)의 시간복잡도

 

동작 과정

1. 탐색 시작 노드를 스택에 삽입하고 방문 처리
2. 스택의 최상단 노드의 인접 노드 확인
   • 방문하지 않는 인접 노드가 있으면, 그 인접 노드 스택에 넣고 방문 처리
   • 방문하지 않은 인접 노드가 없으면, 스택에서 최상단 노드 꺼내기
3. 2번의 과정을 더 이상 수행할 수 없을 때까지 반복

 

5-8. DFS 예제

const dfs = (graph, v, visited) => {
  //1. 탐색 시작 노드 방문 처리
  visited[v] = true;
  console.log(v);
  
  //2. 탐색 노드의 인접 노드 확인 
  for(const cur of graph[v]){
    if(!visited[cur]){
      dfs(graph, cur, visited);
    }
  }
}

let graph = [
  [],
  [2, 3, 8],
  [1, 7],
  [1, 4, 5],
  [3, 5],
  [3, 4],
  [7],
  [2, 6, 8],
  [1, 7],
]

let visited = [...Array(9).fill(false)];

dfs(graph, 1, visited);

 

 

BFS (Breadth-First Search)

• 너비 우선 탐색, 가까운 노드부터 탐색하는 알고리즘
• 큐 이용
• 탐색 수행 시 O(n)의 시간복잡도

참고) 일반적으로 DFS보다 BFS 구현이 조금 더 빠르게 동작한다.

 

 

동작 과정

1. 탐색 시작 노드를 큐에 삽입하고 방문 처리
2. 큐에서 노드를 꺼내고, 해당 노드의 인접 노드 중 방문하지 않는 노드를 모두 큐에 넣고 방문 처리
3. 2번의 과정을 더 이상 수행할 수 없을 때까지 반복

 

5-9. BFS 예제

• 연결리스트로 구현한 Queue사용했다. n의 크기가 작다면 그냥 배열로 구현해도 무방하다.

const bfs = (graph, start, visited) => {
  //1. 탐색 시작 노드 큐에 넣고 방문 처리
  const q = new Queue();
  q.enqueue(start);
  visited[start] = true;

  while (!q.empty()) {
    const v = q.dequeue();
    console.log(v);
    
    //2. 탐색 노드의 인접 노드 확인 
    for(const cur of graph[v]){
      if(!visited[cur]){
        q.enqueue(cur);
        visited[cur] = true;
      }
    }
  }
}

let graph = [
  [],
  [2, 3, 8],
  [1, 7],
  [1, 4, 5],
  [3, 5],
  [3, 4],
  [7],
  [2, 6, 8],
  [1, 7],
]

let visited = [...Array(9).fill(false)];

bfs(graph, 1, visited);

 

참고) 배열 큐 사용 예시

const bfs = (graph, start, visited) => {
  const q = [];
  q.push(start);
  visited[start] = true;

  while (q.length !== 0) {
    const v = q.shift();
    console.log(v);
    
    for(const cur of graph[v]){
      if(!visited[cur]){
        q.push(cur);
        visited[cur] = true;
      }
    }
  }
}

 

 

실전 문제

1. 그래프 형태로 모델링
   • 인접 정점 탐색 방식 확인
     • 인접 행렬 → 방향키로 상하좌우 탐색
     • 인접 리스트 → 인접 정점 개수만큼 반복문으로 탐색
2. 탐색 방식 선택
   • 각 정점을 한 번씩 방문 → DFS/BFS
   • 백트래킹 → DFS
   • 최단경로 → BFS

 

음료수 얼려 먹기

• 단순히 모든 정점을 탐색하는 문제로 DFS와 BFS 중 아무거나 선택해 풀면 된다.

 

입력 정제

const fs = require('fs');
let input = fs.readFileSync("./tc.txt").toString().trim().split('\n');

const [nm, ...arr] = input;
const [n, m] = nm.split(' ').map(v => +v);
const graph = arr.map(v1 => v1.split(''));

 

BFS 풀이

const dir = [[0, 1], [0, -1], [1, 0], [-1, 0]];
const visited = Array.from(Array(n), () => Array(m).fill(false));

const bfs = (graph, sx, sy) => {
  const q = [];
  q.push([sx, sy]);
  visited[sx][sy] = true;

  while (q.length !== 0) {
    const [x, y] = q.shift();

    for (let i = 0; i < 4; i++) {
      const nx = x + dir[i][0];
      const ny = y + dir[i][1];

      if (nx < 0 || nx >= n || ny < 0 || ny >= m)
        continue;

      if (!visited[nx][ny] && graph[nx][ny] === '0') {
        q.push([nx, ny]);
        visited[nx][ny] = true;
      }
    }
  }
}

function solution(n, m, graph) {
  let count = 0;

  for (let i = 0; i < n; i++) {
    for (let j = 0; j < m; j++) {
      const cur = graph[i][j];
      if (!visited[i][j] && cur === '0') {
        bfs(graph, i, j);
        count++;
      }
    }
  }

  return count;
}

console.log(solution(n, m, graph));

 

DFS 풀이

const dir = [[0, 1], [0, -1], [1, 0], [-1, 0]];
const visited = Array.from(Array(n), () => Array(m).fill(false));

const dfs = (graph, x, y) => {
  visited[x][y] = true;
  
  for(let i = 0; i < 4; i++){
    const nx = x + dir[i][0];
    const ny = y + dir[i][1];

    if(nx < 0 || nx >= n || ny < 0 || ny >= m)
      continue;

    if(!visited[nx][ny] && graph[nx][ny] === '0'){
      dfs(graph, nx, ny);
    }
  }
}

function solution(n, m, graph) {
  let count = 0;

  for (let i = 0; i < n; i++) {
    for (let j = 0; j < m; j++) {
      const cur = graph[i][j];
      if (!visited[i][j] && cur === '0') {
        dfs(graph, i, j);
        count++;
      }
    }
  }
  
  return count;
}

console.log(solution(n, m, graph));

 

미로 탈출

• 최단 경로 문제로 BFS로 풀었을 때 효과적이다.

const fs = require('fs');
let input = fs.readFileSync("./tc.txt").toString().trim().split('\n');

const [nm, ...arr] = input;
const [n, m] = nm.split(' ').map(v => +v);
const graph = arr.map(v1 => v1.split('').map(v2 => +v2));

const dir = [[0, 1], [0, -1], [1, 0], [-1, 0]];
const visited = Array.from(Array(n), () => Array(m).fill(false));

const bfs = (graph, sx, sy) => {
  const q = [];
  q.push([sx, sy]);
  visited[sx][sy] = true;

  while (q.length !== 0) {
    const [x, y] = q.shift();

    for (let i = 0; i < 4; i++) {
      const nx = x + dir[i][0];
      const ny = y + dir[i][1];

      if (nx < 0 || nx >= n || ny < 0 || ny >= m)
        continue;

      if (!visited[nx][ny] && graph[nx][ny]) {
        q.push([nx, ny]);
        visited[nx][ny] = true;
        graph[nx][ny] = graph[x][y] + 1;
      }
    }
  }
}

function solution(n, m, graph) {
  bfs(graph, 0, 0);
  return graph[n - 1][m - 1];
}

console.log(solution(n, m, graph));

 

방문 처리를 별도로 하지 않는 경우

• 별도의 방문 처리 visited를 두지 않아도 되는 문제이다.
• graph[nx][ny] === 1로 처음 방문 여부를 확인하기만 하면 이동 가능한 칸만 움직일 수 있다.
• 다만 탐색 후 graph를 출력해보면, 중복 방문이 이루어진 칸을 볼 수 있는데 이는 정답을 도출하는데 영향이 없기 때문에 괜찮다. 문제에서는 단순히 가장 오른쪽 아래 위치로 이동하는 것을 요구하고 있기 때문이다.

const dir = [[0, 1], [0, -1], [1, 0], [-1, 0]];

const bfs = (graph, sx, sy) => {
  const q = [];
  q.push([sx, sy]);

  while (q.length !== 0) {
    const [x, y] = q.shift();

    for (let i = 0; i < 4; i++) {
      const nx = x + dir[i][0];
      const ny = y + dir[i][1];

      if (nx < 0 || nx >= n || ny < 0 || ny >= m)
        continue;

      // 해당 노드를 처음 방문하는 경우에만 최단 거리 기록
      if (graph[nx][ny] === 1) {
        q.push([nx, ny]);
        graph[nx][ny] = graph[x][y] + 1;
      }
    }
  }
}