[백준](Java) 2606 - 바이러스

민지킴·2021년 5월 18일
0

백준

목록 보기
12/48
post-thumbnail

문제 링크

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

문제 풀이

bfs로 접근을 해서 풀었고
그래프를 2차원 배열로 바꾸고 풀었다.

시작이 1번 컴퓨터 이므로 computer[1][j]를 돌며서 1이며 chk[j]가 false인 값을 찾는다. 그 값은 queue에 넣어서 다음에 탐색하도록 한다.


코드

import java.util.*;


public class Main {

    static int[][] computer;
    static boolean[] chk;
    static int n;
    static int m;

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);

        n = sc.nextInt();
        m = sc.nextInt();
        computer = new int[n + 1][n + 1];

        chk = new boolean[n + 1];

        for (int i = 0; i < m; i++) {
            int y = sc.nextInt();
            int x = sc.nextInt();
            computer[y][x] = 1;
            computer[x][y] = 1;
        }
        //System.out.println(Arrays.deepToString(computer));
        System.out.println(bfs(1));

    }

    public static int bfs(int idx) {
        int answer = 0;
        Queue<Integer> queue = new LinkedList<>();
        queue.add(idx);
        chk[idx] = true;
        while (!queue.isEmpty()) {
            idx = queue.poll();
            for (int i = 1; i <= n; i++) {
                if (computer[idx][i] == 1 && !chk[i]) {
                    queue.add(i);
                    chk[i]= true;
                    computer[i][idx] = 0;
                    answer++;
                }
            }
        }


        return answer;
    }
}

profile
하루하루는 성실하게 인생 전체는 되는대로

0개의 댓글