[JAVA 자바] 백준 2606번 : 바이러스

▶ 문제

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

2606번: 바이러스

 

▶ 설명

방문한 노드의 개수를 구하는 것이므로 DFS나 BFS 둘 중 아무거나 사용해서 구현할 수 있다.

나는 DFS로 구현해 보았다.

 

앞선 그래프 순회 단계의 문제들와 비슷하다. 

처음 방문하는 노드번호가 주어진다는 점, 방문한 노드의 개수에서 1개 노드를 제외시켜 카운트 시켜야 한다는 점만 주의하면 될 것이다.

 

 

 

🌱 풀이

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.StringTokenizer;

public class Main {
	static boolean check[];
	static ArrayList<ArrayList<Integer>> graph = new ArrayList<>();
	static int cnt;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;

		int n = Integer.parseInt(br.readLine());
		int m = Integer.parseInt(br.readLine());

		check = new boolean[n + 1];

		for (int i = 0; i < n + 1; i++) {
			graph.add(new ArrayList<Integer>());
		}

		while (m-- > 0) {
			st = new StringTokenizer(br.readLine(), " ");
			int u = Integer.parseInt(st.nextToken());
			int v = Integer.parseInt(st.nextToken());

			graph.get(u).add(v);
			graph.get(v).add(u);
		}

		cnt = 0;
		dfs(1);
		System.out.println(cnt);

	}

	private static void dfs(int node) {
		check[node] = true;

		for (int i = 0; i < graph.get(node).size(); i++) {
			int newNode = graph.get(node).get(i);
			if (!check[newNode]) {
				cnt++;
				check[newNode] = true;
				dfs(newNode);
			}
		}
	}
}

 

 

---

방문한 노드를 체크할 boolean 배열을 선언한다. 노드 번호는 인덱스를 가리키므로 편의상 인덱스 1부터 시작하도록 하고, 배열의 크기도 1을 더해준다.

 

방문할 노드의 개수는 cnt 변수에 담긴다.

1번 컴퓨터를 제외한 나머지 컴퓨터의 개수를 구해야 하므로 0으로 초기화 시켜준다.

 

그리고, dfs 함수를 호출할 때 1번 컴퓨터부터 시작하므로 1을 인수로 넣어준다.

 

 

 

 

▶ Log