[백준] 바이러스 2606번 - Java

[백준] 바이러스 2606번

나의 풀이

public class Virus {
    static int N, M;
    static int[][] network;
    static boolean[] visited;
    static int count = 0;

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

        network = new int[101][101];
        visited = new boolean[101];

        for(int i = 0; i < M; i++) {
            String[] s = br.readLine().split(" ");
            int x = Integer.parseInt(s[0]);
            int y = Integer.parseInt(s[1]);

            network[x][y] = network[y][x] = 1;
        }

        int virusComputer = 1;

        bfs(virusComputer);
        System.out.println(count);
    }

    static void bfs(int start) {
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(start);
        visited[start] = true;

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

            for(int i = 1; i <= N; i++) {
                if(!visited[i] && network[computer][i] == 1) {
                    queue.offer(i);
                    visited[i] = true;
                    count++;
                }
            }
        }
    }
}

    network = new int[101][101];
    visited = new boolean[101];

    for(int i = 0; i < M; i++) {
        String[] s = br.readLine().split(" ");
        int x = Integer.parseInt(s[0]);
        int y = Integer.parseInt(s[1]);

        network[x][y] = network[y][x] = 1;
    }

• 범위가 100까지 이기 때문에, 1을 받기 위해 101로 배열들의 사이즈를 초기화 해주었다.
• 간선의 수만큼 반복을 하면서 각 노드를 서로 연결시켜 주었다.

    static void bfs(int start) {
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(start);
        visited[start] = true;

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

            for(int i = 1; i <= N; i++) {
                if(!visited[i] && network[computer][i] == 1) {
                    queue.offer(i);
                    visited[i] = true;
                    count++;
                }
            }
        }
    }

• bfs 를 사용하여 접근하였다.
• 큐를 생성하여 시작하는 컴퓨터 번호를 큐에 넣고 방문처리 해주었다.
• 큐가 비어있지 않은 동안 큐에서 해당 컴퓨터 번호를 꺼내서 해당 컴퓨터와 연결되어 있는 컴퓨터들을 다 탐색하기 시작한다.
• 탐색 과정에서 방문하지 않은 컴퓨터를 찾을 때마다 카운트를 1씩 올려준다.

  int virusComputer = 1;

  bfs(virusComputer);
  System.out.println(count);

• 시작 컴퓨터 번호는 1로 고정되어 있기 때문에 1로 하드코딩을 하였다.
• bfs 로직 수행 후, 증가한 카운트를 출력하면 된다.

느낀점

BFS나 DFS를 구현할 줄만 알면 풀 수 있었다. 다행이다.