바이러스

[hsskey]

바이러스

네트워크를 통해 전파되는 바이러스의 전파 범위를 계산하는 문제

📝 제약조건

• 컴퓨터의 수는 100 이하의 양의 정수
• 컴퓨터는 1번부터 차례대로 번호가 매겨짐
• 네트워크는 양방향 연결

💡 예시

• Input:

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

• Output: 4

문제 해결 과정

Step 1: 문제 이해하기

• 1번 컴퓨터부터 시작하여 연결된 모든 컴퓨터로 바이러스가 전파됨
• 직/간접적으로 연결된 모든 컴퓨터가 감염됨
• 연결되지 않은 컴퓨터는 감염되지 않음 (예: 4, 7번 컴퓨터)

Step 2: 접근 방법

• DFS(깊이 우선 탐색) 활용
  • 1번 컴퓨터부터 시작하여 연결된 모든 컴퓨터를 탐색
  • 방문한 컴퓨터는 visited 배열로 체크
  • 그래프는 인접 리스트로 구현

Step 3: 코드 설계

1. 입력값 처리 및 그래프 초기화
2. 양방향 그래프 구현
3. DFS 함수 구현
   • 방문 처리
   • 연결된 컴퓨터 탐색
4. 감염된 컴퓨터 수 계산 (1번 컴퓨터 제외)

Step 4: 코드 구현

const fs = require('fs')
const filePath = process.platform === 'linux' ? '/dev/stdin' : `${__dirname}/input.txt`
const input = fs.readFileSync(filePath).toString().split('\n')

// 입력값 처리
const n = Number(input[0]) // 정점(컴퓨터)의 개수
const m = Number(input[1]) // 간선(연결)의 개수
let graph = []

// 그래프 초기화
for(let i = 1; i <= n; i++) {
    graph[i] = []
}

for(let i = 2; i <= m + 1; i++) {
    let[x,y] = input[i].split(' ').map(Number)
    graph[x].push(y)
    graph[y].push(x)
}

let cnt = 0
const visited = new Array(n + 1).fill(false)

// DFS 구현
function dfs(v) {
    visited[v] = true // 방문처리
    cnt++
    for(let i of graph[v]) {
        if(!visited[i]) {
            dfs(i)
        }
    }
}

// 1번 컴퓨터부터 시작
dfs(1)
// 1번 컴퓨터를 제외한 감염된 컴퓨터 수 출력
console.log(cnt - 1)

시간 복잡도

• O(V + E): V는 정점의 개수, E는 간선의 개수
• DFS는 모든 정점과 간선을 한 번씩 방문하므로 O(V + E)의 시간 복잡도를 가짐

[hsskey]

방문처리 자료구조를 배열대신 Set을 이용시 더 간단하게 처리가능

...
...

const visited = new Set()
function dfs(v) {
    // 이미 방문처리가 되었다면 return
    if(visited.has(v)) return
    // 방문처리
    visited.add(v)
    cnt++
    for(let i of graph[v]) {
        if(!visited[i]) {
            dfs(i)
        }
    }
}

...
...