[백준(Baekjoon)/JAVA] 2606. 바이러스

 

연결된 컴퓨터를 그래프라고 생각하고 이 그래프를 인접행렬로 나타내었다.

너비우선탐색(BFS) 연습문제이다.

 

insertVertex메소드는 두 점사이의 edge를 표시하여 그래프를 만든다.

visited[]는 점의 방문여부를 표시한다.

bfs에서 처음에 방문했다는 표시로 true를 저장하고,

방문하지 않았을 경우에만 재귀를 불러들여 다시 방문 표시를 한다.

1부터 시작하는데 1컴퓨터는 바이러스에 감염된 컴퓨터에 포함시키지 않는다.

따라서 sum - 1이 답이 된다.

 

package bj;

import java.util.Scanner;

public class bj2606_2 {

	static int[][] V;
	static boolean[] visited;
	static int sum = 0;
	
	public static void insertVertex(int v1, int v2) {
		V[v1][v2] = 1;
		V[v2][v1] = 1;
	}
	
	public static void bfs(int start, int n) {
		visited[start] = true;

		for(int j = 0; j < n; j++) {
			if(V[start][j] == 1 && !visited[j]) {
				bfs(j, n);
			}
		}
		
	}
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		int n = sc.nextInt();
		int m = sc.nextInt();
		
		V = new int[n][n];
		visited = new boolean[n];
		
		for(int i = 0; i < n; i++) {
			for(int j = 0; j < n; j++) {
				V[i][j] = 0;
				visited[j] = false;
			}
		}
		
		for(int i = 0; i < m; i++) {
			int v1 = sc.nextInt();
			int v2 = sc.nextInt();
			insertVertex(v1 - 1, v2 - 1);
		}
		
		bfs(0, n);

		for(int i = 0; i < n; i++) {
			if(visited[i])
				sum++;
		}
		
		System.out.println(sum-1);

	}
	

}

 

계속 안되길래 반례를 찾았다

4 

3 
1 2 
3 4 
2 4

이부분에서 j를 start+1부터로 제한하여 3과4가 연결된 것을 캐치하지 못하고 잘못나왔다.

j를 0에서부터 탐색하는 걸로 수정하여 문제를 맞힐 수 있었다.

 

 

 

 

/0115