[백준] 2606. 바이러스 - 실버3

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

2606번: 바이러스

 

문제 요약

번 컴퓨터가 웜 바이러스에 걸렸다. 컴퓨터의 수와 네트워크 상에서 서로 연결되어 있는 정보가 주어질 때, 1번 컴퓨터를 통해 웜 바이러스에 걸리게 되는 컴퓨터의 수를 출력하는 프로그램을 작성하시오.

한 줄에 한 쌍씩 네트워크 상에서 직접 연결되어 있는 컴퓨터의 번호 쌍이 주어진다.

 

문제 해결 아이디어

입력받은 대로 그래프를 만들어서 dfs 혹은 bfs 탐색을 해 주면 되는 간단한 문제다.

 

완성된 코드

package week4;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.StringTokenizer;

public class Main {
	/*
	 84ms
	 */
	static int N;
	static boolean[] visited;
	static LinkedList<LinkedList<Integer>> graph;

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		int M = Integer.parseInt(br.readLine());
		graph = new LinkedList<>();

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

		for (int i = 0; i < M; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine(), " ");
			int x = Integer.parseInt(st.nextToken());
			int y = Integer.parseInt(st.nextToken());
			graph.get(x).add(y);
			graph.get(y).add(x);
		}
		visited = new boolean[N + 1];
		dfs(1);

		int cnt = 0;
		for (int i = 0; i < visited.length; i++) {
			if (visited[i])
				cnt++;
		}
		System.out.println(cnt-1); // 1번 컴퓨터 빼줌
	} // end of main

	public static void dfs(int current) {
		visited[current] = true;
		for (int i = 0; i < graph.get(current).size(); i++) {
			if (!visited[graph.get(current).get(i)]) {
				dfs(graph.get(current).get(i));
			}
		}
	}
}