DFS/BFS - 바이러스

문제

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

분석/설계

전형적인 그래프를 탐색하는 DFS/BFS 유형의 문제이고

그래프 상 노드(컴퓨터)가 100대 이하이므로 완전 탐색으로 접근 가능한 문제로 파악했고

DFS로 구현했습니다.

구현 코드

import java.util.ArrayList;
import java.util.Scanner;

public class Main {
	
	static boolean[] visted;
	static ArrayList<ArrayList<Integer>> graph = new ArrayList<ArrayList<Integer>>();
	
	public static void dfs(int V) {
		visted[V] = true;

		for(int i=0; i<graph.get(V).size(); i++) {
			int W = graph.get(V).get(i);
			if(!visted[W]) dfs(W);	
		}
	}
	
	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		
		int N = scanner.nextInt(); // 컴퓨터 수
		int M = scanner.nextInt(); // 연결된 컴퓨터 쌍의 수
		
		for(int i=0; i<=N; i++) { // 인접 배열 리스트 초기화
			graph.add(new ArrayList<Integer>());
		}
		
		visted = new boolean[N+1]; // 방문 여부 판단할 배열
		
		scanner.nextLine();
		for(int i=0; i<M; i++) { // 인접 배열 리스트 값 세팅 
			int v1 = scanner.nextInt();
			int v2 = scanner.nextInt();
			graph.get(v1).add(v2); 
			graph.get(v2).add(v1);
		}
		
		dfs(1);
		
		int cnt = 0;
		for(int i=0; i<visted.length; i++) {
			if(visted[i]) cnt++;
		}
		System.out.println(cnt-1);
		scanner.close();
	}
}

정리

문제를 읽어보면 1번 컴퓨터부터 시작한다는 조건이 있고 

1번 컴퓨터를 통해 바이러스에 걸리는 컴퓨터 수를 구해야하므로

1번 컴퓨터까지 카운트된 숫자는 제외해줍니다.

참고

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