[백준] 2606: 바이러스 JAVA

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

---

풀이과정

이 문제는 BFS/DFS를 사용해서 푸는 문제이다.

 

BFS/DFS

각각의 구현은 아래 링크를 참고하자

https://jaeyeong04.tistory.com/11

[백준] 1260: DFS와 BFS JAVA

 

풀이 핵심

1. 일단 나는 BFS 쪽 구현에 더 약한 것 같아 연습을 위해 BFS로 구현을 하였다.
2. 주어진 input을 사용하여 adjency matrix를 만든다.
3. matrix와 visited 배열을 사용하여 BFS를 수행하고, 1번 노드를 제외한 방문한 노드의 수를 저장하는 count를 업데이트 한다.

---

최종 코드

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

// The main method must be in a class named "Main".
class Main {
    static int[][] matrix;
    static boolean[] visited;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;
        int numNode = Integer.parseInt(br.readLine());
        matrix = new int[numNode+1][numNode+1];
        visited = new boolean[numNode+1];
        visited[1] = true;
        int numEdge = Integer.parseInt(br.readLine());
        for(int i = 0; i < numEdge; i++){
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            matrix[a][b] = 1;
            matrix[b][a] = 1;
        }
        int answer = bfs();
        bw.write(String.valueOf(answer));
        bw.flush();
    }

    public static int bfs(){
        int count = 0;
        Queue<Integer> queue = new LinkedList<>();
        queue.add(1);
        while(!queue.isEmpty()){
            //pivot은 이번에 방문한 노드
            int pivot = queue.remove();
            for(int i = 1; i < matrix.length; i++){
                int target;
                if(matrix[pivot][i] == 1 && visited[i] == false){
                    queue.add(i);
                    visited[i] = true;
                    matrix[pivot][i] = 0;
                    matrix[i][pivot] = 0;
                    count++;
                }
            }
        }
        return count;
    }
}