[백준2606] 바이러스

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

2606번: 바이러스

문제설명

컴퓨터는 네트워크를 통해 연결되어있다. (이것을 읽으면 딱 그래프가 연상된다)

1번 컴퓨터가 웜바이러스가 걸렸고, 이 컴퓨터와 네트워크를 통해 연결되었다면, 모두 바이러스에 걸리게된다. 

이때, 1번 컴퓨터를 통해 웜바이러스에 걸린 컴퓨터의 대수는?

 

문제 해결 방법

BFS를 이용하였고, 큐를 통해 구현하였다. 

코드 구현

import java.io.BufferedWriter;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;
import java.util.Arrays;
import java.util.Queue;
import java.util.LinkedList;

public class Main {
	public static int N, M;
	public static int cnt = 0;
	public static boolean[] visited;
	public static int[][] graph;
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st;
		N = Integer.parseInt(br.readLine());
		M = Integer.parseInt(br.readLine());
		
		visited = new boolean[N];
		graph = new int[N][N];
		
		Arrays.fill(visited, false);
		for(int i = 0; i < N; i++) {
			Arrays.fill(graph[i], 0);
		}
		
		
		for(int i = 0; i < M; i++) {
			st = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			graph[a - 1][b - 1] = 1;
			graph[b - 1][a - 1] = 1;
		}
		bfs(0);
		System.out.println(cnt);
		
	}
	
	public static void bfs(int start) {
		Queue<Integer> q = new LinkedList<Integer>();
		q.offer(start);
		
		while(!q.isEmpty()) {
			int nodeIndex = q.poll();
			
			
			if(!visited[nodeIndex]) {
				visited[nodeIndex]= true;
			}
			
			for(int i = 0; i < N; i++) {
				if(graph[nodeIndex][i] == 1 && !visited[i]) {
					visited[i] = true;
					cnt+=1;
					q.offer(i);
				}
			}
		}
	}
}

 

시간/공간 복잡도

O(N^2)

최적화 및 개선

따로 하지않음

어려웠던 점

아직 살짝 문법적으로 헷깔리는점이 어려울뿐 ㅎㅎ