[백준 (Baekjoon)] (java) 문제 2606 - bfs

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

2606번: 바이러스

1) 접근법

인접 배열 map과 1차원 배열 visited, 그리고 queue를 이용하여 bfs를 구현하여 풀었다. 

 

2) 시간 복잡도

start node인 컴퓨터1 (map에서는 index 0)에 연결되어 있는 컴퓨터들을 확인한다. 모든 컴퓨터가 컴퓨터1과 연결이 되어있지 않을수도 있기에 통상적으로 말하는 bfs의 시간복잡도인 V*O(V) = O(V^2)보다는 시간이 적게걸릴 것이다.

 

3) 이 문제로 얻은 것 + 소감

BFS에 관한 이해

 

4) 코드

package BFS_DFS;

import java.util.*;
import java.io.*;

public class p2606_bfs {
    static BufferedReader br;
    static StringTokenizer tok;

    static int N;   //number of computers
    static int M;   //number of edges
    static int[][] map;
    static boolean[] visited; 

    public static void main(String[] args) throws IOException{
        br = new BufferedReader(new InputStreamReader(System.in));

        N = Integer.parseInt(br.readLine());
        M = Integer.parseInt(br.readLine());
        map = new int[N][N];
        visited = new boolean[N];
        for(int[] m:map){
            Arrays.fill(m,0);
        }
        Arrays.fill(visited, false);       

        for(int i=0;i<M;i++){
            tok = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(tok.nextToken())-1;
            int b = Integer.parseInt(tok.nextToken())-1;
            map[a][b] = 1;
            map[b][a] = 1;
        }

        System.out.println(bfs(0));
    }
    
    public static int bfs(int start){
        Queue<Integer> queue = new LinkedList<>();
        queue.add(start);
        visited[start] = true;
        
        int count = 0;

        while(!queue.isEmpty()){
            int p = queue.poll();

            for(int i=0;i<N;i++){
                if(!visited[i] && map[p][i]==1){
                    queue.add(i);
                    count++;
                    visited[i]=true;
                }
            }
        }

        return count;
    }
}