백준 2606. 바이러스 (JAVA)

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

public class Main {
	
	static int ComCnt, Ssang;
	static int[][] arr;
	static boolean[] visit;
	static int cnt = 0;
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st ;
		
		ComCnt = Integer.parseInt(br.readLine());
		Ssang = Integer.parseInt(br.readLine());
		
		arr = new int[ComCnt + 1][ComCnt + 1];
		visit = new boolean[ComCnt + 1];
		
		for(int i = 1 ; i <= Ssang; i++) {
			
			st = new StringTokenizer(br.readLine());
			
			int num1 = Integer.parseInt(st.nextToken());
			int num2 = Integer.parseInt(st.nextToken());
			
			arr[num1][num2] = 1;
			arr[num2][num1] = 1;
		}
	
		System.out.println(dfs(1) - 1);
	}
	
	static int dfs(int num) {
		
			visit[num] = true;
			cnt++;
			
			for(int i = 1 ; i <= ComCnt; i++) {
				
				if(arr[num][i] == 1 && !visit[i]) {	
					
					dfs(i);
				}
			}
		return cnt;
	}
}

○ 문제 요약

한 컴퓨터에 바이러스가 걸리면 해당 컴퓨터와 연결되어 있는 컴퓨터들도 바이러스에 걸린다고 한다. 그때, 바이러스가 걸린 1번 컴퓨터로 인해 바이러스가 걸리는 컴퓨터는 몇 개인지 출력해라.

○ 문제 풀이

백준 1260. DFS와 BFS(JAVA)

이전에 포스팅한 1260번 문제와 같이 DFS 또는 BFS 알고리즘을 사용해 풀 수 있는 문제이다. 이번 문제에서는 DFS만 사용해서 문제를 풀어보도록 하겠다. 

 

먼저 컴퓨터의 수에 1을 더한 값을 배열들의 크기로 정해주었다. 

그리고 컴퓨터끼리 연결되어 있는 수(=Ssang)만큼 입력을 받고 arr 배열에 연결되어 있는 상태를 1로 표시해주었다.

그러면 dfs() 메소드를 만드는 것을 제외하고 다른 준비는 끝났다고 봐도 무방하다.

 

dfs() 메소드를 보면 1번 컴퓨터를 기준으로 하기 때문에 변수 값에 1을 넣으면서 메소드가 실행된다.

메소드가 시작하면서 1은 방문한 상태이므로 visit[1] = true로 방문했다는 표시를 남긴다. 그리고 감염된 컴퓨터의 수를 cnt++해서 하나 올려준다.

 

그리고 for문으로 들어가서 if문 조건을 확인하는데 arr[1][1] 은 1도 아닐뿐더러 visit[1] 도 true이기 때문에 if문을 통과하지 못하고 i++되어 i = 2가 된다. i가 2가 된 상태에서 다시 if문을 들어가면 arr[1][2]는 1이고 visit[2]는 false이기 때문에 if문을 통과하면서 dfs(2)를 호출한다. 이 과정을 계속 수행하면 1 -> 2 -> 3-> 5 -> 6 순서로 방문하는 것을 알 수 있다. 

최종적으로 감염된 컴퓨터는 5개라는 것을 알 수 있지만 문제를 보면 1번 컴퓨터로 인해 감염된 컴퓨터의 개수를 출력하는 것이다. 

고로 1번 컴퓨터는 제외한 나머지 컴퓨터의 개수를 출력해야하므로 -1을 해줘 출력하도록 하자. 

○ 결과