백준 2606번: 바이러스

1번 컴퓨터와 연결된 컴퓨터들의 개수를 구하는 문제이다.

 

위의 예시의 4번과 7번 컴퓨터처럼, 동떨어진 컴퓨터를 제외한 컴퓨터의 개수를 구하면 된다.

 

즉, 1번 컴퓨터에서 갈 수 있는 컴퓨터들을 표시해준 후에, 해당 컴퓨터 개수를 출력하도록 한다.

 

 

 

package bakjoon2606.virus;

import java.util.Scanner;

public class Main {
	static int[][] arr;
	static boolean[] visited;
	static int n;
	public static void main(String args[]) {
		Scanner sc = new Scanner(System.in);
		n = sc.nextInt();
		int v = sc.nextInt();
		arr = new int[n+1][n+1];
		visited = new boolean[n+1];
		int tmp1=0;
		int tmp2=0;
		for(int i=0;i<v;i++) {
			tmp1 = sc.nextInt();
			tmp2 = sc.nextInt();
			arr[tmp1][tmp2] =1;
			arr[tmp2][tmp1] =1;
		}
		
		dfs(1);
		
		int result = 0;
		for(int i=2;i<=n;i++) {
			if(visited[i])
				result++;
		}
		
		System.out.println(result);
	}
	public static void dfs(int x) {
		
		visited[x] = true;
		
		for(int i=1;i<=n;i++) {
			if(arr[x][i]==1 && !visited[i]) {
				dfs(i);
			}
		}
		
	}
}

 

bfs든 dfs든 상관이 없다.

visited 배열에 갔다 왔는지 여부를 작성해주기 때문에, visited 가 true 인 컴퓨터의 개수에서 1번 컴퓨터만 빼고 출력해주도록 한다.

 

아니면, dfs에 들어갈 때마다 cnt란 변수의 개수를 증가시켜준 후에, cnt-1의 값을 출력해줘도 좋다.

조건에 맞을 경우만 dfs라는 재귀를 호출하기 때문에, 위처럼 해줘도 가능하다.