백준 2606 바이러스(Java)

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

2606번: 바이러스

---

 

해석 및 팁

 

---

 

이 문제는 dfs 활용하면 쉽게 풀 수 있습니다. boolean배열을 선언한 후에 입력받은 값을 true로 넣어줍니다. 그다음 dfs함수를 정의하여 visit배열에 넣고 반복문을 통해 감염되는 컴퓨터를 찾습니다. 감염이 되지 않았고 길이 연결되어 있으면 그 수를 dfs함수에 넣어서 다시 찾습니다. 컴퓨터의 개수를 출력하면 되므로 count를 출력해 주면 됩니다.

 

---

 

Java 코드

 

---

import java.util.Scanner;

public class Main {
  
  static boolean[][] arr;
  static boolean[] visit;
  static int count;
  static int n;
  static int m;
  
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    StringBuilder sb = new StringBuilder();

    n = sc.nextInt();
    m = sc.nextInt();
    count = 0;

    arr = new boolean[n+1][n+1];
    visit = new boolean[n+1];

    for(int i = 1; i <= m; i++) {
      int x = sc.nextInt();
      int y = sc.nextInt();
      arr[x][y] = arr[y][x] = true;
    }

    dfs(1);

    
    System.out.println(count);
  }

  public static void dfs(int num) {
    visit[num] = true;
    for(int i = 1; i <= n; i++) {
      if(!visit[i] && arr[num][i] == true) {
        count++;
        dfs(i);
      }
    }
  }

}