[백준][DFS][난이도:하] 바이러스 (2606번)

1.  문제

■ URL : https://www.acmicpc.net/problem/2606

■ 난이도 : 하 (DFS 기본문제)

 

2. 핵심요약

■ 예제입력

    - 첫째 줄: 컴퓨터의 수 → 노드 수
    - 둘째 줄: 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수 → 간선의 수
    - 셋째 줄이하 : 간선 정보

7 6 1 2 2 3 1 5 5 2 5 6 4 7

 

■ "예제 입력"을 "그래프"로 표현

 

■ "그래프"를 "인접리스트"로 표현

0
1	2, 5
2	1, 3, 5
3	2
4	7
5	1, 2, 6
6	5
7	4

 

3. 문제풀이 접근

■ 그래프에서 1번 노드를 시작으로 연결된 모든 노드의 갯수를 카운트한다. (DFS, BFS)

 

4. JavaScript 코딩

// 로컬 환경에서 입력을 받을지, stdin에서 받을지 결정하는 변수
let isLocal = true;
 
let fs = require('fs'); // 파일 시스템 모듈을 사용하여 파일 읽기
let input;
 
// 로컬 환경일 경우 파일에서 입력을 읽어옴, 그렇지 않으면 stdin에서 읽어옴
if (isLocal) {
    input = fs.readFileSync('./2606.txt').toString().split('\n'); // 파일에서 입력 받기
} else {
    input = fs.readFileSync('/dev/stdin').toString().split('\n'); // stdin에서 입력 받기
}
 
// 첫 번째 줄: 노드의 개수(nodeCnt)와 간선의 개수(edgeCnt) 입력 받기
let nodeCnt = Number(input[0]); // nodeCnt: 노드의 개수
let edgeCnt = Number(input[1]); // edgeCnt: 간선의 개수
 
// 그래프 초기화 (1): 각 노드에 연결된 다른 노드들을 저장할 배열
// let graph = Array(nodeCnt + 1).fill([]); // 이렇게 하면 모든 항목이 동일한 배열을 참조하게 되어 문제가 발생할 수 있음
// 위와 같은 방식은 각 항목이 동일한 참조를 가지므로, 하나의 항목을 수정하면 다른 항목에 영향이 미친다.
 
// 그래프 초기화 (2): 각 항목에 대해 별도의 빈 배열을 할당하여 독립적인 배열을 생성한다.
// 각 항목에 대해 별도의 빈 배열을 할당하여 독립적인 배열을 생성하므로, 수정이 다른 항목에 영향을 주지 않는다.
graph = [];
for (let i = 0; i < nodeCnt + 1; i++) {
    graph[i] = [];      // 각 노드에 연결된 다른 노드들을 저장할 빈 배열 생성
}
 
// visited 초기화
// fill()을 사용하여 참조형 값(객체나 배열)을 채우는 경우, 그 참조가 모든 배열 요소에 적용된다.
// 즉, 객체나 배열을 채우면 모든 항목이 동일한 객체나 배열을 참조한다.
// 반면, true나 false 같은 원시 값은 값 자체가 할당되기 때문에 배열 내의 각 요소는 서로 독립적으로 존재한다.
let visited = Array(nodeCnt + 1).fill(false);       // 방문 여부를 추적하는 배열 (각 노드는 방문되지 않은 상태로 시작)
 
// input 데이터를 읽고 그래프에 간선 정보를 추가
const START_LINE = 2; // 간선 정보는 2번째 줄부터 시작
for (let i = START_LINE; i < START_LINE + edgeCnt; i++) {
    let [nodeSrc, nodeDst] = input[i].split(' ').map(Number);   // 간선의 두 노드
    graph[nodeSrc].push(nodeDst);   // nodeSrc와 nodeDst를 연결
    graph[nodeDst].push(nodeSrc);   // nodeDst와 nodeSrc를 연결 (무방향 그래프)
}
 
 // 감염된 노드의 수를 저장할 변수
let answer = 0;
 
// 깊이 우선 탐색(DFS) 함수
const dfs = (graph, currNode, visited) => {
    visited[currNode] = true; // 현재 노드를 방문 처리
    answer += 1; // 현재 노드를 감염된 노드로 카운트
 
    // 현재 노드와 연결된 다른 노드들에 대해 재귀적으로 DFS 호출
    for (nextNode of graph[currNode]) {
        if (!visited[nextNode]) { // 아직 방문하지 않은 노드에 대해 DFS 탐색
            dfs(graph, nextNode, visited);
        }
    }
}
 
// 노드 1에서 시작하여 DFS를 실행 (노드 1부터 감염이 시작된다고 가정)
dfs(graph, 1, visited);
 
// 출력: 감염된 노드 수에서 시작 노드(1번 노드)를 제외하고 출력
console.log('감염된 Node 수:', answer - 1); // 시작 노드를 제외한 감염된 노드 수 출력
 

 

5. 참고

https://languagestory.tistory.com/380

[DFS] 개념(Depth First Search; 깊이 우선 탐색) - 자바스크립트