알고리즘 수업 - 너비 우선 탐색 1 (opens in a new tab)

문제 해결 방법

인접 정점은 오름차순으로 방문한다
무방향 그래프이기 때문에, 그래프를 그릴 때 정점 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배 이상 빠른 것을 볼 수 있었다.

01 Understand Binary Search 1072