[BaekJoon] 백준 2606번 _ 바이러스 for JAVA _ DFS 알고리즘

 

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

2606번: 바이러스

 

 

 

문제

 

 

 

---

 

위의 문제는 DFS, BFS 모두 사용할 수 있을 것 같다.

 

 

 

나는 DFS를 먼저 연습할 거라서 DFS로 풀었다.

 

 

 

 

DFS 사용 시

 

 

 

 

DFS를 사용하면 순서는 1 - 2 - 3 - 5 - 6 이 되어 4가 return될 것이다. (1은 포함x)

 

 

 

이전에 풀었던 1260번과 아주 유사한 문제이다 (https://ticssfm.tistory.com/67)

 

 

 

 

 

코드

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 Baek2606 {
	public static ArrayList<ArrayList<Integer>> array = new ArrayList<ArrayList<Integer>>();
	public static boolean[] visited = new boolean[101]; // 컴터 최대 100대
	public static int count = 0;
	
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int com = Integer.parseInt(br.readLine());
		int couple = Integer.parseInt(br.readLine());
		
		for(int i = 0; i < 10001; i++) // 100대의 컴 모두 연결되면 선 10000개
			array.add(new ArrayList<Integer>()); // 초기화 
			
		
		for(int i = 0; i < couple; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine(), " ");
			int x = Integer.parseInt(st.nextToken());
			int y = Integer.parseInt(st.nextToken());
			array.get(x).add(y);
			array.get(y).add(x);
		}
		
		for(int i = 0; i < com + 1; i++)
			Collections.sort(array.get(i)); // 오름차순 정렬
		
		if(dfs(1)) System.out.println(count - 1);  //맨 처음 시작점 1을 제외하기 위해 -1 해줌
		
	}
	
	public static boolean dfs(int x) {
		visited[x] = true;
		count ++;
		
		for(int i = 0; i < array.get(x).size(); i++) {
			int y = array.get(x).get(i);
			if(!visited[y]) {
				dfs(y);
			}
		}
		return true;
	}
}

 

 

 

 

 

 

 

성능