백준 2606번 바이러스 (JavaScript 풀이)

🔍 DFS vs BFS 비교 - 백준 2606번으로 이해하기

 

📖 그래프 탐색이란?

 

정의: 연결된 모든 노드를 빠짐없이 방문하는 것
목적: 특정 노드 찾기, 경로 찾기, 연결 여부 확인
핵심: 그래프라는 자료구조에서 모든 데이터를 체계적으로 훑어보는 방법!

---

DFS vs BFS 비교

	DFS (깊이 우선)	BFS (너비 우선)
탐색 방식	🏃‍♂️ 한 방향으로 끝까지!	🌊 퍼져나가듯이!
자료구조	📚 스택(Stack) / 재귀	🎯 큐(Queue)
메모리 사용	적음 (O(깊이))	많음 (O(너비))
최단거리	❌ 보장 안됨	✅ 보장됨
구현 난이도	쉬움 (재귀)	보통 (큐 사용)
코드 길이	짧음	조금 김

 

---

DFS (Depth-First Search) - 깊이 우선 탐색

DFS 핵심 포인트 : "한 길로 끝까지 가보고, 막히면 되돌아와서 다른 길 가기!"

🏠 집에서 열쇠 찾기 비유  방 하나 들어가서 구석구석 다 뒤져보기  없으면 나와서 다른 방 가기  각 방을 완전히 다 확인하고 넘어감

예시 그래프로 이해하기

      1 (시작)
     / \
    2   3
   / \ / \
  4  5 6  7

DFS 동작 과정

실시간 탐색 과정:  1번 방문 → "2와 3 중 어디 갈까? 왼쪽부터!"  2번 방문 → "4와 5 중 어디 갈까? 왼쪽부터!"  4번 방문 → "더 갈 곳이 없네, 돌아가자"  2번으로 복귀 → "이제 5번 가보자"  5번 방문 → "여기도 막혔네, 돌아가자"  1번으로 복귀 → "이제 3번 가보자"  3번 방문 → "6과 7 중 왼쪽부터!"  6번, 7번 순서로 방문   최종 방문 순서: 1 → 2 → 4 → 5 → 3 → 6 → 7

 

---

💻 DFS 코드 구현 

 

javascript

// 재귀 방식 - 가장 직관적인 방식
const fs = require('fs');
const input = fs.readFileSync(0, 'utf8').trim().split('\n');

function dfs(graph, node, visited) {
    visited[node] = true;
    console.log(node); // 방문한 노드 출력
    
    // 현재 노드와 연결된 모든 노드들 확인
    for (let neighbor of graph[node]) {
        if (!visited[neighbor]) {
            dfs(graph, neighbor, visited); // 재귀 호출이 핵심!
        }
    }
}

// 사용 예시
const graph = {
    1: [2, 3],
    2: [1, 4, 5],
    3: [1, 6, 7],
    4: [2],
    5: [2],
    6: [3],
    7: [3]
};

const visited = Array(8).fill(false);
dfs(graph, 1, visited);

---

 

javascript

// 스택 방식 - 재귀 대신 반복문으로!
const fs = require('fs');
const input = fs.readFileSync(0, 'utf8').trim().split('\n');

function dfsStack(graph, start) {
    const visited = Array(8).fill(false);
    const stack = [start];
    
    while (stack.length > 0) {
        const node = stack.pop(); // 스택은 LIFO (Last In First Out)
        
        if (!visited[node]) {
            visited[node] = true;
            console.log(node);
            
            // 주의: 역순으로 넣어야 올바른 순서!
            for (let i = graph[node].length - 1; i >= 0; i--) {
                if (!visited[graph[node][i]]) {
                    stack.push(graph[node][i]);
                }
            }
        }
    }
}

---

BFS (Breadth-First Search) - 너비 우선 탐색

BFS 핵심 포인트 : "물방울이 퍼져나가듯이 가까운 곳부터 차례대로!"

🎆 불꽃놀이 비유  중심에서 시작해서 동심원으로 퍼져나감  1단계 → 2단계 → 3단계 순서로  거리별로 레벨을 나누어 탐색

BFS 동작 과정

실시간 탐색 과정: 1번 방문 → 큐: [2, 3] "1번의 이웃들 줄 서!" 2번 방문 → 큐: [3, 4, 5] "2번의 이웃들도 뒤에 줄 서!" 3번 방문 → 큐: [4, 5, 6, 7] "3번의 이웃들도!" 4번, 5번, 6번, 7번 순서대로 방문   최종 방문 순서: 1 → 2 → 3 → 4 → 5 → 6 → 7   레벨별로 보면:  레벨 0: 1  레벨 1: 2, 3  레벨 2: 4, 5, 6, 7

 

---

💻 BFS 코드 구현

 

javascript

// BFS는 큐를 사용! (JavaScript에서는 배열로 구현)
const fs = require('fs');
const input = fs.readFileSync(0, 'utf8').trim().split('\n');

function bfs(graph, start) {
    const visited = Array(8).fill(false);
    const queue = [start]; // 큐 초기화
    visited[start] = true;
    
    while (queue.length > 0) {
        const node = queue.shift(); // 큐는 FIFO (First In First Out)
        console.log(node);
        
        // 현재 노드의 모든 이웃들 확인
        for (let neighbor of graph[node]) {
            if (!visited[neighbor]) {
                visited[neighbor] = true;
                queue.push(neighbor); // 큐 뒤쪽에 추가
            }
        }
    }
}

---

🚀 백준 2606번 바이러스 - 실전 적용

📋 문제 요약

• 목표: 1번 컴퓨터와 연결된 모든 컴퓨터 개수 구하기
• 방법: 그래프 탐색 (DFS 또는 BFS)
• 주의: 1번 컴퓨터는 개수에서 제외!

1. DFS 해결 코드

 

javascript

const fs = require('fs');
const input = fs.readFileSync(0, 'utf8').trim().split('\n');

const N = Number(input[0]); // 컴퓨터 개수
const M = Number(input[1]); // 연결 개수

// 인접 리스트로 그래프 생성
const graph = Array.from({ length: N + 1 }, () => []);

// 연결 정보 입력 (양방향!)
for (let i = 0; i < M; i++) {
  const [a, b] = input[i + 2].split(' ').map(Number);
  graph[a].push(b); // a → b 연결
  graph[b].push(a); // b → a 연결 (양방향이니까!)
}

// 방문 체크 배열
const visited = Array(N + 1).fill(false);

// DFS 함수
function dfs(node) {
  visited[node] = true;
  
  for (let neighbor of graph[node]) {
    if (!visited[neighbor]) {
      dfs(neighbor);
    }
  }
}

// 1번 컴퓨터부터 시작!
dfs(1);

// 1번 제외하고 감염된 컴퓨터 개수 세기
let count = 0;
for (let i = 2; i <= N; i++) {
  if (visited[i]) count++;
}

console.log(count);

---

2. BFS 해결 코드

javascript

// BFS 버전 (DFS 대신 이 부분만 바꾸면 됨)
function bfs(start) {
  const queue = [start];
  visited[start] = true;
  
  while (queue.length > 0) {
    const node = queue.shift();
    
    for (let neighbor of graph[node]) {
      if (!visited[neighbor]) {
        visited[neighbor] = true;
        queue.push(neighbor);
      }
    }
  }
}

bfs(1);
// 나머지 코드는 동일!

---

🤔 언제 뭘 써야 할까?

	DFS	BFS
사용하는 경우	경로 존재 여부만 확인 (백준 2606번) 연결된 컴포넌트 찾기 메모리 절약이 중요할 때 백트래킹 문제 (순열, 조합) 사이클 검출	최단 거리 구하기 (가중치 없는 그래프) 레벨별 탐색 필요 동시 시작점 여러 개 미로 탈출 (최단 경로)
대표 문제들	백준 2606: 바이러스 백준 11724: 연결 요소의 개수 백준 2667: 단지번호붙이기	백준 2178: 미로 탐색 백준 7576: 토마토 백준 1697: 숨바꼭질

 

---

💭 내 생각

• 처음엔 DFS가 복잡해 보였는데, "끝까지 가고 돌아오기"로 생각하니 쉬워짐!
• BFS는 "동심원처럼 퍼지기"를 떠올리면 이해하기 쉬움
• 재귀 DFS가 가장 직관적이지만, 깊이가 깊으면 스택 버전이 안전함
• 백준 문제 풀 때는 대부분 DFS면 충분 ! BFS는 최단거리 문제에서 장점인듯 !