[백준] JavaScript - 바이러스 (2606)

개요

문제 이름: 바이러스 (2606)
문제 링크: https://www.acmicpc.net/problem/2606
플랫폼: 백준
알고리즘 분류: DFS
소요 시간: 2시간

 

문제 전문

설명

입출력

문제 풀이

해설

이 문제는 주어진 컴퓨터 네트워크에서 1번 컴퓨터가 웜 바이러스에 감염되었을 때, 1번 컴퓨터와 직접 또는 간접적으로 연결된 컴퓨터 중에서 웜 바이러스에 감염되는 컴퓨터의 총 개수를 구하여 출력해야 하는 문제입니다.

 

DFS 알고리즘을 사용하여 그래프를 탐색하는 전형적인 예시라고 할 수 있겠습니다. 그래프를 생성하고, 시작점(1번 컴퓨터)부터 DFS 탐색을 수행하여 연결된 컴퓨터들을 방문하고, 방문한 컴퓨터의 수를 세어주는 과정으로 해결할 수 있습니다. 사실상 주어진 네트워크 상에서 1번 컴퓨터와 직접 또는 간접적으로 연결된 모든 컴퓨터의 수를 구하는 것이 목표입니다.

 

먼저, 입력으로 주어진 컴퓨터의 수와 연결 정보를 바탕으로 그래프를 생성합니다. 이때 인접 리스트 형태로 그래프를 표현하면 효율적입니다. 각 컴퓨터의 방문 여부를 체크하기 위한 visited 객체도 생성합니다.

 

그래프 생성이 완료되면 1번 컴퓨터부터 DFS 탐색을 시작합니다. DFS는 재귀적으로 동작하며, 현재 컴퓨터를 방문 처리하고 인접한 컴퓨터 중 아직 방문하지 않은 컴퓨터를 재귀적으로 탐색합니다.

 

이 과정에서 1번 컴퓨터와 직접 또는 간접적으로 연결된 모든 컴퓨터를 방문하게 됩니다. 마지막으로, visited 객체를 순회하면서 1번 컴퓨터를 통해 감염된 컴퓨터의 수를 세어 최종적으로 출력합니다.

 

시도

1차 시도  (성공)

const fs = require("fs");
const input = fs.readFileSync("/dev/stdin").toString().trim().split("\n");

const n = parseInt(input[0]); // 컴퓨터의 수
const m = parseInt(input[1]); // 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수
const graph = {}; // 객체로 그래프 표현
const visited = {}; // 각 컴퓨터의 방문 여부

// 그래프 생성
for (let i = 1; i <= n; i++) {
	graph[i] = [];
	visited[i] = false;
}

for (let i = 2; i < m + 2; i++) {
	const [a, b] = input[i].split(" ").map(Number);
	graph[a].push(b);
	graph[b].push(a);
}

// DFS 함수
function dfs(v) {
	visited[v] = true;
	for (let i = 0; i < graph[v].length; i++) {
		const next = graph[v][i];
		if (!visited[next]) {
			dfs(next);
		}
	}
}

// 1번 컴퓨터부터 DFS 탐색
dfs(1);

// 1번 컴퓨터를 통해 감염되는 컴퓨터의 수 계산
let count = 0;
for (let i = 2; i <= n; i++) {
	if (visited[i]) {
		count++;
	}
}

console.log(count);

해당 문제가 풀리려면 기본적으로 다음과 같은 과정을 거쳐야 합니다.

1. 입력받은 정보를 바탕으로 그래프를 생성합니다.
2. 이때 객체를 사용하여 그래프를 표현하고, 각 컴퓨터의 방문 여부를 저장하기 위한 객체도 생성합니다.
3. DFS 함수를 정의합니다.
4. DFS 함수는 현재 방문한 컴퓨터를 방문 처리하고, 해당 컴퓨터와 연결된 모든 컴퓨터를 재귀적으로 방문합니다.
5. 1번 컴퓨터부터 DFS를 수행합니다.
6. 그리고 DFS가 완료되면, 1번 컴퓨터를 제외한 방문한 컴퓨터의 수를 세어 결과를 출력합니다.

그리고 위의 코드는 이러한 로직을 기반으로 작성되었습니다. 아래는 상세한 설명입니다.

1. 입력값을 받아와 변수에 저장합니다. n은 컴퓨터의 수, m은 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수입니다.
2. graph 객체를 사용하여 그래프를 표현합니다. 각 키는 컴퓨터의 번호이고, 값은 해당 컴퓨터와 연결된 컴퓨터의 번호를 저장하는 배열입니다.
3. visited 객체를 사용하여 각 컴퓨터의 방문 여부를 저장합니다. 초기값은 모두 false입니다.
4. 입력값을 바탕으로 그래프를 생성합니다. 연결된 컴퓨터 쌍의 번호를 graph 객체에 추가합니다.
5. dfs 함수를 정의합니다. 현재 방문한 컴퓨터를 방문 처리하고, 해당 컴퓨터와 연결된 모든 컴퓨터를 재귀적으로 방문합니다.
6. 1번 컴퓨터부터 dfs 함수를 호출하여 DFS 탐색을 시작합니다.
7. DFS 탐색이 완료되면, 1번 컴퓨터를 제외한 방문한 컴퓨터의 수를 세어 count 변수에 저장합니다.
8. count 값을 출력합니다.

 

사용된 주요 메서드

• parseInt(str): 문자열을 정수로 변환합니다. 입력받은 컴퓨터의 수와 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수를 정수로 변환하기 위해 사용되었습니다.
• split(separator): 문자열을 주어진 구분자를 기준으로 나누어 배열로 반환합니다. 입력받은 컴퓨터 쌍의 번호를 분리하기 위해 사용되었습니다.
• map(callback): 배열의 각 요소에 대해 주어진 콜백 함수를 실행하고, 그 결과를 새로운 배열로 반환합니다. 분리된 컴퓨터 쌍의 번호를 정수로 변환하기 위해 사용되었습니다.
• push(element): 배열의 끝에 새로운 요소를 추가합니다. 그래프에서 각 컴퓨터와 연결된 컴퓨터의 번호를 추가하기 위해 사용되었습니다.

 

시간 복잡도 및 공간 복잡도

• 시간 복잡도: O(n + m)
  • 그래프 생성: O(m), m은 연결된 컴퓨터 쌍의 수입니다.
  • DFS 탐색: O(n + m), 각 컴퓨터를 한 번씩 방문하고, 각 연결된 간선을 한 번씩 탐색하므로 O(N+M)의 시간 복잡도를 가집니다.
    (n은 컴퓨터의 수, m은 연결된 컴퓨터 쌍의 수)
  • 감염된 컴퓨터 수 계산: O(n), n은 컴퓨터의 수입니다.
  • 즉, 전체 시간 복잡도는 O(n + m)입니다.
• 공간 복잡도: O(n + m)
  • 그래프: O(n + m) , 인접 리스트로 그래프를 표현하였으므로 O(n + m) 의 공간이 필요합니다.
    (n은 컴퓨터의 수, m은 연결된 컴퓨터 쌍의 수)
  • 방문 여부 객체: O(n), n은 컴퓨터의 수입니다. 각 컴퓨터의 방문 여부를 저장하는 데 O(n)의 공간이 필요합니다.
  • 즉, 전체 공간 복잡도는 O(n + m) 입니다.