알고리즘 수업 - 너비 우선 탐색 1

• https://www.acmicpc.net/problem/24444

오늘의 학습 키워드

BFS

• 정점과 같은 레벨에 있는 노드(형제 노드)를 먼저 탐색하는 방식
• 큐 자료구조를 사용하여 인접한 정점들의 리스트를 관리한다

문제 해결 방법

• 인접 정점은 오름차순으로 방문한다
• 무방향 그래프이기 때문에, 그래프를 그릴 때 정점 u와 정점 v는 양방향임을 고려한다
• BFS를 활용해 문제를 해결한다
  1. 시작 노드를 큐에 넣고 방문 처리한다
  2. 큐에서 원소를 꺼내어 방문하지 않은 인접 노드가 있는지 확인한다
     • 있다면, 방문하지 않은 인접 노드를 큐에 모두 삽입하고 방문 처리한다
  3. 2번 과정을 더 이상 반복할 수 없을 때까지 반복한다.

코드

연결리스트로 구현

class Queue {
  constructor() {
    this.items = {};
    this.headIndex = 0;
    this.tailIndex = 0;
  }
  enqueue(item) {
    this.items[this.tailIndex] = item;
    this.tailIndex += 1;
  }
  dequeue() {
    const item = this.items[this.headIndex];
    delete this.items[this.headIndex];
    this.headIndex += 1;
    return item;
  }
  peek() {
    return this.items[this.headIndex];
  }
  get length() {
    return this.tailIndex - this.headIndex;
  }
  get isEmpty() {
    return this.length === 0;
  }
}

// input
const fs = require("fs");
const filePath = process.platform == "linux" ? "/dev/stdin" : "./input.txt";
const [[N, M, R], ...edges] = fs
  .readFileSync(filePath)
  .toString()
  .trim()
  .split("\n")
  .map((line) => line.split(" ").map(Number));

// G (graph)
const G = Array.from(new Array(N + 1), () => []);

edges.forEach(([u, v]) => {
  G[u].push(v);
  G[v].push(u);
});

G.forEach((node) => node.sort((a, b) => a - b));

// BFS
const visited = new Array(N + 1).fill(0);
const Q = new Queue();

Q.enqueue(R);
let visitOrder = 1;

while (!Q.isEmpty) {
  const cur = Q.dequeue();

  if (!visited[cur]) {
    visited[cur] = visitOrder;
    visitOrder += 1;

    G[cur].forEach((next) => {
      if (!visited[next]) Q.enqueue(next);
    });
  }
}

// output
console.log(visited.slice(1).join("\n"));

배열로 구현

// input
const fs = require("fs");
const filePath = process.platform == "linux" ? "/dev/stdin" : "./input.txt";
const [[N, M, R], ...edges] = fs
  .readFileSync(filePath)
  .toString()
  .trim()
  .split("\n")
  .map((line) => line.split(" ").map(Number));

// G (graph)
const G = Array.from(new Array(N + 1), () => []);

edges.forEach(([u, v]) => {
  G[u].push(v);
  G[v].push(u);
});

G.forEach((node) => node.sort((a, b) => a - b));

// BFS
const visited = Array(N + 1).fill(0);

function bfs(node) {
  const Q = [];
  let visitOrder = 1;

  Q.push(node);

  while (Q.length !== 0) {
    const cur = Q.shift();

    if (!visited[cur]) {
      visited[cur] = visitOrder;
      visitOrder += 1;

      G[cur].forEach((next) => {
        if (!visited[next]) Q.push(next);
      });
    }
  }
}

bfs(R);

// output
console.log(visited.slice(1).join("\n"));

첫 시도는 아래와 같은 이유로 연결리스트로 구현했다

• 정점들 간의 연결 상황을 간편하게 볼 수 있음
• 메모리 사용이 적어 효율적으로 메모리 사용 가능
  (인접행렬의 경우 nxn 개의 저장공간을 필요로 함 ~> 상대적으로 더 많은 메모리 사용)
• 그러나 시간복잡도 면에 있어서 훨씬 좋다 (코드 구현은 어렵지만..)

실제로 시간 복잡도와 메모리가 얼마나 차이나는지 궁금해서 각각 연결리스트와 배열을 이용해 큐를 구현해 문제를 푼 결과,

(17분 전 코드 : 연결리스트 / 3분 전 코드 : 배열)

확실히 연결리스트로 구현한 코드의 시간이 배열로 구현한 코드보다 3배 이상 빠른 것을 볼 수 있었다.