[BackJoon] 백준 2606 바이러스(DFS)

백준 DFS 문제

#2606 - 바이러스(Virus)

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

사용한 개념

 DFS깊이탐색을 이용했습니다.

문제를 보면, 결국 무조건 1과 연결되어 있는 컴퓨터 갯수를 새는 것입니다.

컴퓨터 1과 연결되어 있으면 계속 깊이탐색을 해서 연결된 컴퓨터 갯수를 카운트하면 답은 쉽게 나옵니다. 컴퓨터 1과 연결되어있지 않는 또 다른 네트워크 영역은 신경쓸 필요도 없습니다.

따라서 소스에서 보면 알 수 있듯이 DFS(1)을 주어 무조건 시작은 1번 컴퓨터에서 시작함을 알 수 있습니다.

DFS 기본 개념을 이해하면 쉽게 풀수있고 DFS를 잘 모르면, 어렵습니다.

저는 기본적으로 인접리스트 방식의 DFS 깊이탐색을 했습니다.

혹, DFS 기본개념을 모르시면 아래 링크에서 공부하시면 됩니다.

2017/10/04 - [전공지식/ Data structure / Algorithm] - [Algorithm] DFS 깊이탐색

전체소스

package BackJoon.DFS;

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

public class Virus {

	static ArrayList<Integer>[] a;
	static boolean[] visit;
	static int n; //점의수
	static int l; //간선의 수	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		 n = sc.nextInt(); //점의 수
		 l = sc.nextInt(); //간선의 수(연결된 선의 수)
		
		a = new ArrayList[n+1];
		visit = new boolean[n+1];
		
		for(int i=0; i<n+1; i++) a[i] = new ArrayList<>();
		
		for(int i=0; i<l; i++){
			int u = sc.nextInt();
			int v = sc.nextInt();
			a[u].add(v);
			a[v].add(u);
		}
		
		
		DFS(1);

		
		int ans = 0;
		for(boolean f : visit){
			if(f == true) ans++;
		}
		System.out.println(ans-1);
		
	}
	
	
	private static void DFS(int u) {
		visit[u] = true;
		
		for(int v : a[u]){
			if(visit[v] == false) DFS(v);
		}
	}

}