[JAVA/DFS/BFS] 백준 2606 : 바이러스

문제 링크

1. DFS와 스택을 사용한 풀이

import java.io.*;
import java.util.*;

class Main{
	public static void main(String[] args) throws IOException {
		// 컴퓨터의 갯수와 링크 갯수 입력
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		int m = Integer.parseInt(br.readLine());
		// 컴퓨터의 갯수(인덱스 1부터 취급)만큼 list 생성
		ArrayList<ArrayList<Integer>> list = new ArrayList<ArrayList<Integer>>();
		for(int i=0; i<=n; i++) {
			list.add(new ArrayList<Integer>());
		}
		// 링크 갯수만큼 입력받고 arraylist에 담아주기
		for(int i=0; i<m; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			list.get(a).add(b);
			list.get(b).add(a);
		}
		// dfs 실행하기 위한 boolean 배열과 스택
		boolean[] visited = new boolean[n+1];
		Stack<Integer> st = new Stack<Integer>();
		// dfs 실행
		st.push(1);
		visited[1]=true;
		while(!st.isEmpty()) {
			int idx = st.pop();
			for(int i=0; i<list.get(idx).size(); i++) {
				int y = list.get(idx).get(i);
				if(!visited[y]) {
					st.push(y);
					visited[y]=true;
				}
			}
		}
		// 1번 컴퓨터를 제외한 바이러스 감염 컴퓨터 count
		int cnt = -1;
		for(boolean b:visited) {
			if(b) cnt++;
		}
		System.out.println(cnt);
	}
}

2. DFS와 재귀함수를 사용한 풀이

        // dfs 메서드 실행
		dfs(1);
		int cnt = -1;
		for(boolean b:visited) {
			if(b) cnt++;
		}
		System.out.println(cnt);
	}
	
    // dfs 메서드
	public static void dfs(int x) {
		visited[x]=true;
		for(int i=0; i<list.get(x).size(); i++) {
			int y = list.get(x).get(i);
			if(!visited[y]) dfs(y);
		}
	}
	
}

3. BFS를 이용한 풀이

	bfs(1);
		int cnt = -1;
		for(boolean b:visited) {
			if(b) cnt++;
		}
		System.out.println(cnt);
	}
	
	public static void bfs(int start) {
		Queue<Integer> q = new LinkedList<Integer>();
		q.offer(start);
		visited[start]=true;
		while(!q.isEmpty()) {
			int x = q.poll();
			for(int i=0; i<list.get(x).size(); i++) {
				int y = list.get(x).get(i);
				if(!visited[y]) {
					q.offer(y);
					visited[y]=true;
				}
			}
		}
	}