[백준알고리즘-JAVA]2606번 풀이(바이러스) - 초보도 이해하는 풀이

안녕하세요

인포돈 입니다.

백준 알고리즘 2606번 풀이입니다. 

* 참고사항
 - 개발환경은 eclipse을 기준으로 작성되었습니다.
 - java언어를 이용하여 문제를 풀이합니다.
 - 알고리즘 문제는 풀이를 보고 해답을 찾는 것도 중요하지만 무엇보다 스스로 풀이를 시도해봐야 합니다!!
(해당 풀이를 보기 전 충분히 문제에 대해 고민해봐야 합니다!)
 - 해당 풀이 말고도 수많은 풀이 방법이 존재합니다.

---

백준 2606 (바이러스)

문제

신종 바이러스인 웜 바이러스는 네트워크를 통해 전파된다. 한 컴퓨터가 웜 바이러스에 걸리면 그 컴퓨터와 네트워크 상에서 연결되어 있는 모든 컴퓨터는 웜 바이러스에 걸리게 된다.

 

예를 들어 7대의 컴퓨터가 <그림 1>과 같이 네트워크 상에서 연결되어 있다고 하자. 1번 컴퓨터가 웜 바이러스에 걸리면 웜 바이러스는 2번과 5번 컴퓨터를 거쳐 3번과 6번 컴퓨터까지 전파되어 2, 3, 5, 6 네 대의 컴퓨터는 웜 바이러스에 걸리게 된다. 하지만 4번과 7번 컴퓨터는 1번 컴퓨터와 네트워크상에서 연결되어 있지 않기 때문에 영향을 받지 않는다.

어느 날 1번 컴퓨터가 웜 바이러스에 걸렸다. 컴퓨터의 수와 네트워크 상에서 서로 연결되어 있는 정보가 주어질 때, 1번 컴퓨터를 통해 웜 바이러스에 걸리게 되는 컴퓨터의 수를 출력하는 프로그램을 작성하시오.

입력

첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 11번부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어진다. 이어서 그 수만큼 한 줄에 한 쌍씩 네트워크 상에서 직접 연결되어 있는 컴퓨터의 번호 쌍이 주어진다.

출력

1번 컴퓨터가 웜 바이러스에 걸렸을 때, 1번 컴퓨터를 통해 웜 바이러스에 걸리게 되는 컴퓨터의 수를 첫째 줄에 출력한다.

입력, 출력 예제

성공 코드

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 Main {

	static boolean[] check;
	static int[][] arr;
	static int count = 0;
	
	static int node, line;
	
	static Queue<Integer> q = new LinkedList<>();

	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		
		node = Integer.parseInt(br.readLine());
		line = Integer.parseInt(br.readLine());
	
		arr = new int[node+1][node+1];
		check = new boolean[node+1];
		
		for(int i = 0 ; i < line ; i ++) {
			StringTokenizer str = new StringTokenizer(br.readLine());
			
			int a = Integer.parseInt(str.nextToken());
			int b = Integer.parseInt(str.nextToken());
			
			arr[a][b] = arr[b][a] =  1;	
		}
		
			dfs(1);
			
			System.out.println(count-1);
		
		}
	public static void dfs(int start) {
		
		check[start] = true;
		count++;
		
		for(int i = 0 ; i <= node ; i++) {
			if(arr[start][i] == 1 && !check[i])
				dfs(i);
		}
		
	}
	
}

바이러스 알고리즘은 쉽게 해결할 수 있었습니다. 앞서 BFS와 DFS를 풀어보셨다면, 해당 코드를 약간만 변형한다면 쉽게 풀리기 때문이죠. 즉, 기본적인 DFS, BFS의 기본적인 활용 문제라고 보시면 됩니다.

STEP을 따라가며 쉽게 이해해보도록 하죠

---

알고리즘 흐름도

 입력 받기 -> 인접 행렬에 값 넣어주기 -> DFS 실행하기 -> 출력하기

---

STEP1 입력 받기 및 인접 행렬 값 넣어주기

		node = Integer.parseInt(br.readLine());
		line = Integer.parseInt(br.readLine());
	
		arr = new int[node+1][node+1];
		check = new boolean[node+1];
		
		for(int i = 0 ; i < line ; i ++) {
			StringTokenizer str = new StringTokenizer(br.readLine());
			
			int a = Integer.parseInt(str.nextToken());
			int b = Integer.parseInt(str.nextToken());
			
			arr[a][b] = arr[b][a] =  1;	
		}

뭐 별거 없습니다. 처음에 NODE의 개수

두 번째 입력은 line 즉 간선의 개수

 

세 번째부터는 연결된 노드의 쌍을 입력받습니다.

 

받은 값은 arr[a][b] = a [b][a] = 1의 값을 넣어줍니다. 양쪽에 다 넣어주는 이유는 1, 2나 2,1이나 같은 의미이기 때문이죠

 

arr [][] 은 인접 행렬을 표현하기 위한 배열

check []은 이미 바이러스에 감염되었는지를 판단하는 배열의 역할을 수행합니다

---

STEP2 DFS 구현하기

	public static void dfs(int start) {
		
		check[start] = true;
		count++;
		
		for(int i = 0 ; i <= node ; i++) {
			if(arr[start][i] == 1 && !check[i])
				dfs(i);
		}
		
	}

사실 이번 문제는 DFS든 BFS든 어떠한 방법으로도 구할 수 있습니다.

 

DFS의 경우 별거 없습니다. 처음 값으로는 1을 줍니다.

바이러스에 감염되었으니 1을 COUNT 해줍니다.

 

자 그다음 FOR문을 돌립니다.

만약 인접 행렬의 시작 노드와 연결된 값이 1이라면 확인합니다 CHECK로 이미 감연 된 노드인지

만약에 둘 다 맞다면, DFS를 해당 노드로 다시 실행합니다.

 

그렇게 된다면 다음은 1번 노드와 연결된 다음 노드의 CHECK에 TRUE가 입력되고 또 COUNT가 세어집니다.

 

이러한 식으로 DFS가 구현됩니다.

 

물론 처음 DFS를 접해보시면 구하기 힘들겠지만, 많이 풀어봐야 합니다!

---