[백준/JAVA] 2606 바이러스

DFS와 BFS

백준 2606번 바이러스 문제 링크

풀이

• 인접행렬 방식
• "1" 에서 시작, 자동으로 1의 visited = true
• 인접행렬 arr에서 1과 연관된 노드면 visited를 판단 -> false면 큐에 저장, true면 다른 값 탐색
• 큐에 저장하면서 count 값 증가
• 반복해서 큐가 비일경우 종료

---

제출 코드

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

class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int N = Integer.parseInt(br.readLine());
        int M = Integer.parseInt(br.readLine());

        int[][] arr = new int[N+1][N+1];
        boolean[] visited = new boolean[N+1];

        Queue<Integer> q = new LinkedList<>();

        for (int i = 0; i < M; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine(), " ");
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            arr[a][b] = arr[b][a] = 1;
        }

        int start = 1;
        int count = 0;
        q.add(start);
        visited[start] = true;

        while (!q.isEmpty()) {
            start = q.poll();

            for (int i = 1; i < N+1; i++) {
                if (arr[start][i] == 1 && !visited[i]) {
                    q.add(i);
                    visited[i] = true;
                    count++;
                }
            }
        }
        for (int i = 1; i <= M+1; i++) {
            for (int j = 1; j <= M+1; j++) {
                bw.write(arr[i][j] + " ");
            }
            bw.flush();
            bw.newLine();
        }
        bw.write(String.valueOf(count));
        bw.flush();
    }
}

---

입력

7
6
1 2
2 3
1 5
5 2
5 6
4 7

---

인접 행렬로 저장된 형태

0 1 0 0 1 0 0 
1 0 1 0 1 0 0 
0 1 0 0 0 0 0 
0 0 0 0 0 0 1 
1 1 0 0 0 1 0 
0 0 0 0 1 0 0 
0 0 0 1 0 0 0

---

후기

범위가 적어서 인접행렬로 가능했는데...
다음 문제부터는 인접리스트 방식으로 풀어야겠다.