[JAVA]백준 2606번: 바이러스

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

2606번: 바이러스

 

 

 

| 문제 해결방법

 

관련 알고리즘 : bfs + 인접행렬

 

1. 입력받은 네트워크 쌍을 이용해 인접행렬을 초기화 한다.

 

2. (1,1) 부터 시작하여 네트워크로 연결되어 있는 컴퓨터를 모두 탐색한다.( bfs + visited[] )

 

3. visited[] (방문한 컴퓨터는 true가 됨) 배열에서 true의 개수를 반환(1번 컴퓨터는 counting하지 않음)

 

 

 

[JAVA] 해설 코드

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

public class Main {

	static int V,E;
	static int[][] arr;
	static Queue<Integer> q = new LinkedList<>();
	static boolean[] visited;
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		V = Integer.parseInt(br.readLine());	
		E = Integer.parseInt(br.readLine());
		arr = new int[V+1][V+1];
		visited = new boolean[V+1];
		for(int i=0;i<E;i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			int s = Integer.parseInt(st.nextToken());
			int e = Integer.parseInt(st.nextToken());
			arr[e][s] = arr[s][e] = 1;
		}
		q.offer(1);
		
		bfs();
		
		int result=0;
        // 1번 컴퓨터를 제외하고 연결된 컴퓨터의 개수 구하기
		for(int i=2;i<=V;i++) {
			if(visited[i]) result++;
		}
		System.out.println(result);
		
	}
	private static void bfs() {
		visited[1]=true;
		while(!q.isEmpty()) {
			int s=q.poll();

			for (int i = 1; i <= V; i++) {
				// 연결되어 있다면 큐에 넣기 
				if (arr[s][i] == 1 && visited[i] == false) {

					q.offer(i);
					visited[i] = true;

				}
			}

		}
		
	}

}

 

 

[제출] 메모리 및 시간