💡문제 분석 요약

• 입력: 첫 번째 줄에 정점의 개수 N, 간선의 개수 M, 시작할 정점 V가 주어진다. 이후 M개의 줄에 두 정점 사이의 간선 정보가 주어진다. 간선은 양방향이다.
• 목표: 시작 정점 V에서 DFS와 BFS를 수행한 결과를 각각 출력해야 한다.
  • DFS는 재귀적으로 깊이 우선 탐색을 하여 방문할 수 있는 모든 정점을 탐색한다.
  • BFS는 큐를 사용하여 너비 우선 탐색을 수행하며, 시작점에서 가까운 정점부터 차례대로 탐색한다.

💡알고리즘 설계

• 그래프 표현
  • 그래프는 인접 리스트 방식으로 표현한다.
  • 각 정점이 다른 정점과 연결된 정보를 배열에 저장하여 구현한다.
  • 주어진 그래프가 양방향이므로 각 간선에 대해 두 정점을 서로 연결해 준다.
• 정렬
  • DFS와 BFS 모두 정점 번호가 작은 순서대로 방문해야 하므로 인접 리스트에 저장된 정점들을 오름차순으로 정렬한다.
• DFS(Depth-First Search)
  • 재귀 함수를 사용하여 구현한다. 시작 정점에서 연결된 정점들을 하나씩 재귀적으로 탐색하며, 이미 방문한 정점은 다시 방문하지 않는다.
  • 방문할 때마다 결과를 기록하고 출력한다.
• BFS(Breadth-First Search)
  • 큐를 사용하여 구현한다.
  • 시작 정점에서 가까운 정점부터 차례대로 탐색하며, 큐에 방문할 정점을 넣고, 이미 방문한 정점은 다시 큐에 넣지 않는다.
  • BFS 탐색 순서대로 결과를 기록하고 출력한다.

💡코드

const fs = require('fs');
const path = require('path');

const input = fs.readFileSync(path.join(__dirname, 'input.txt')).toString().trim().split('\\n');

// 입력 받기
const [N, M, V] = input[0].split(' ').map(Number);
const graph = Array.from({ length: N + 1 }, () => []); // 정점의 개수만큼 배열 생성

for (let i = 1; i <= M; i++) {
  const [a, b] = input[i].split(' ').map(Number);
  graph[a].push(b); // 양방향 그래프이므로 양쪽에 연결
  graph[b].push(a);
}

// 정점 번호가 작은 순서대로 방문해야 하므로 정렬
graph.forEach((adjList) => adjList.sort((a, b) => a - b));

// DFS 함수 (재귀적 방식)
const dfs = (start, visited) => {
  visited[start] = true;
  process.stdout.write(start + ' '); // 탐색 순서 출력

  for (const neighbor of graph[start]) {
    if (!visited[neighbor]) {
      dfs(neighbor, visited);
    }
  }
};

// BFS 함수 (큐 방식)
const bfs = (start) => {
  const visited = Array(N + 1).fill(false);
  const queue = [start];
  visited[start] = true;

  while (queue.length) {
    const node = queue.shift(); // 큐에서 꺼낸 노드를 방문
    process.stdout.write(node + ' ');

    for (const neighbor of graph[node]) {
      if (!visited[neighbor]) {
        visited[neighbor] = true;
        queue.push(neighbor); // 큐에 인접 노드 추가
      }
    }
  }
};

// DFS 탐색
const visitedDFS = Array(N + 1).fill(false);
dfs(V, visitedDFS);
process.stdout.write('\\n');

// BFS 탐색
bfs(V);

💡시간 복잡도

• 그래프에서의 탐색은 정점 수 N과 간선 수 M에 비례하는 시간이 걸린다.
  • DFS: 모든 정점을 방문하고 각 정점의 인접 리스트를 순회하므로 O(N + M)의 시간 복잡도를 갖는다.
  • BFS: 마찬가지로 모든 정점과 간선을 순회하므로 O(N + M)의 시간 복잡도를 갖는다.
• 두 알고리즘 모두 시간 복잡도는 O(N + M)이다.