[JAVA]BOJ(백준) - 바이러스 - 2606

- 문제 내용

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

2606번: 바이러스

---

- 문제 접근 방법

전에 풀었던 'DFS와 BFS' 문제를 이용하면 되는 문제이다. 바이러스에 감염된 시작 컴퓨터에서 부터 간선이 연결된 컴퓨터들만 연결되는 것이므로 시작 컴퓨터로부터 간선이 이어지지 않은 컴퓨터는 신경 쓸 필요가 없다고 생각한다. 어차피 재귀 과정에서 간선이 연결된 것들만 방문하면서 바이러스 감염여부를 판단하기 때문!!

따라서 풀이과정은 간단해진다!

아 그리고 DFS, BFS 방법 두개로 풀어봤다.

---

- 풀이

• 입력값 및 DFS 부분

public class BOJ_2606 {
	static int N; // 컴퓨터 수 = 정점의 수
	static int M; // 컴퓨터를 연결시키는 네트워크 수 = 간선의 수
	static int[][] arr; // 연결된 컴퓨터들(간선) 표시할 배열
	static boolean[] check; // 방문 배열
	static int count = 0; // 바이러스 감염된 컴퓨터 수 = 방문된 점점 수
	
	public void virus_dfs(int v) {
		check[v]=true; //현재 감염 컴퓨터 정점 방문처리
		
		for(int i=1; i<=N; i++) { //1~N번 컴퓨터까지 검사시작
			if(arr[v][i]==1 && !check[i]) { //간선 존재하고 방문안했던 정점일때
				virus_dfs(i); // 매개변수로 다음 방문할 감염 컴퓨터(정점) 넣어줌
				count++; // 출력할 count 증가
			}
		}
	}

 

• BFS 부분

public int virus_bfs(int v) {
		Queue<Integer> queue = new LinkedList<Integer>();
		queue.add(v);
		check[v]=true;
		int count = 0;
		
		while(!queue.isEmpty()) {
			int temp = queue.poll();
			
			for(int i=1; i<=N; i++) {
				if(arr[temp][i]==1 && !check[i]) {
					queue.add(i);
					check[i]=true;
					count++;
				}
			}
		}
		return count;
	}

---

• 전체코드

package org.boj.dfs.bfs;

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

public class BOJ_2606 {
	static int N; // 컴퓨터 수 = 정점의 수
	static int M; // 컴퓨터를 연결시키는 네트워크 수 = 간선의 수
	static int[][] arr; // 연결된 컴퓨터들(간선) 표시할 배열
	static boolean[] check; // 방문 배열
	static int count = 0; // 바이러스 감염된 컴퓨터 수 = 방문된 점점 수
	
	/**
	 * DFS 방식 - 재귀
	 * @param v
	 */
	public void virus_dfs(int v) {
		check[v]=true; //현재 감염 컴퓨터 정점 방문처리
		
		for(int i=1; i<=N; i++) { //1~N번 컴퓨터까지 검사시작
			if(arr[v][i]==1 && !check[i]) { //간선 존재하고 방문안했던 정점일때
				virus_dfs(i); // 매개변수로 다음 방문할 감염 컴퓨터(정점) 넣어줌
				count++; // 출력할 count 증가
			}
		}
	}
	
	
	/**
	 * BFS 방식 - 큐
	 * @param v
	 * @return
	 */
	public int virus_bfs(int v) {
		Queue<Integer> queue = new LinkedList<Integer>();
		queue.add(v);
		check[v]=true;
		int count = 0;
		
		while(!queue.isEmpty()) {
			int temp = queue.poll();
			
			for(int i=1; i<=N; i++) {
				if(arr[temp][i]==1 && !check[i]) {
					queue.add(i);
					check[i]=true;
					count++;
				}
			}
		}
		return count;
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		N = Integer.parseInt(br.readLine()); // 정점개수(컴퓨터 개수)
		M = Integer.parseInt(br.readLine()); // 간선개수
		
		arr = new int[N+1][N+1]; //1~N까지 확인 할꺼라 N+1로
		check = new boolean[N+1]; // 위와 마찬가지
		
		for(int i=1; i<=M; i++) { //간선수만큼 돌면서 간선 추가.
			StringTokenizer st = new StringTokenizer(br.readLine());
			int v1 = Integer.parseInt(st.nextToken());
			int v2 = Integer.parseInt(st.nextToken());
			
			arr[v1][v2]=1;
			arr[v2][v1]=1;
		}
		
		new BOJ_2606().virus_dfs(1); //DFS
		for(int i=0; i<check.length; i++) {
			if(check[i]) {check[i]=false;}
		}
		System.out.println(new BOJ_2606().virus_bfs(1)); //BFS 출력값
		System.out.println(count); //DFS 출력값
	}
}

---

- 마치며

DFS의 경우 재귀호출하면서 여러 지역내에서 도는라서 count를 전역변수로해서 감염숫자를 셋다.

그리고 함수 시작부분에 count++을 하면 1을 포함하는거라 if문의 조건이 걸릴 경우만 증가 시켜줬다.

count를 전역변수로 처리하는 이유는 !

DFS도 count를 지역변수로 선언하여 count += virus_dfs(i)+1 로 만들고 return 값을 count로 준다음 함수 종료 후 결과에 +1을 해주면 같은 값이 나오게 할수 있지만 나중에 복잡한 트리구조가 나오면 값이 달라질 고려해야 할꺼같아서 그냥 전역변수로 처리했다.

 

BFS의 경우 어차피 한 지역내에서 탐색해가는 것이기 때문에 count를 지역변수로 주고 return값으로 넘겨준다.