[백준 2606] 바이러스
January 24, 2023
문제
https://www.acmicpc.net/problem/2606
아이디어
- 먼저 입력 값을 가지고 각 컴퓨터간의 연결 여부를 나타내는 2차원 배열과, 각 컴퓨터의 방문 여부를 기록하는 1차원 배열을 초기화한다.
-
그 다음 1번 컴퓨터에 대해서 바이러스를 침투하는 다음 로직을 수행한다.
- 현재 컴퓨터가 이전에 방문한 적이 있던 컴퓨터라면 스킵한다.
- 현재 침투중인 컴퓨터가 1번 컴퓨터가 아니라면 카운트 변수를 증가시킨다.
- 현재 컴퓨터에 대해서 바이러스를 침투하고 방문 여부를 기록한다.
- 현재 컴퓨터와 연결된 모든 컴퓨터에 대해서, 재귀적인 방법으로 바이러스를 침투한다.
소스코드
// 입력 정제
const fs = require("fs");
function getInput(caseID) {
const filePath = process.platform === "linux" ? "/dev/stdin" : `./${__dirname.split('\\').pop()}/i${caseID}.txt`;
const input = fs.readFileSync(filePath).toString().split("\n").map(item => item.trim());
input.pop();
const n = Number(input.shift()); // 컴퓨터의 수
const m = Number(input.shift()); // 연결의 수
const map = Array.from({ length: n + 1 }, () => Array.from({ length: n + 1 }, () => 0));
for (let i = 0; i < m; i++) {
const [a, b] = input.shift().split(" ").map(item => Number(item));
map[a][b] = 1;
map[b][a] = 1;
}
return [n, m, map];
}
// 문제
const [n, m, map] = getInput(1);
const visited = Array.from({ length: n + 1}, () => 0);
let count = 0;
// 해당 번호의 컴퓨터와, 연결된 모든 컴퓨터에 바이러스 침투
function penetrate(num) {
if (visited[num]) return;
if (num !== 1) count++; // 현재 침투중인 컴퓨터가 바이러스 숙주인 1번이 아니라면, 카운트 증가하기
visited[num] = 1;
for (let i = 1; i <= n; i++) {
if (map[num][i]) penetrate(i);
}
}
function solution() {
penetrate(1);
console.log(count);
}
// 실행
solution();