백준 2606 바이러스 자바

바이러스 문제 보러가기

2606번: 바이러스

문제 설명

자바 코드

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {
    static int node[][]; // 그래프 배열
    static boolean isVisited[]; // 방문 배열

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int n= sc.nextInt(); // 컴퓨터의 수
        int m = sc.nextInt(); // 네트워크 상에 연결되어 있는 컴퓨터 쌍의 수 즉, 간선의 수

        node=new int[n+1][n+1];
        isVisited = new boolean[n+1];
        for(int i=0;i<m;i++) { // 그래프 구성
            int a=sc.nextInt();
            int b = sc.nextInt();
            node[a][b]=1;
            node[b][a]=1;

        }

        bfs();

    }

    static void bfs() { // BFS 메소드
        Queue<Integer> queue = new LinkedList<>();

        isVisited[1] =true;
        queue.offer(1);
        int cnt = 0; // 감염 된 컴퓨터의 수
        while(!queue.isEmpty()) {
            int x = queue.poll();

            for(int i=1;i<node.length;i++) { // 차례대로 1번과 연결 된 컴퓨터들을 찾아 cnt변수 증가
                if(node[x][i]==1 && !isVisited[i]) {
                    queue.offer(i);
                    isVisited[i] = true;
                    cnt++;
                }
            }
        }
        System.out.println(cnt); //모든 탐색을 마치고 cnt 출력
    }

}

문제 풀이

이 문제의 경우 BFS를 이용하였습니다.

큐를 이용하여 bfs를 구현하였습니다.