바이러스 - 백준(2606, 그래프 탐색)

🎯 바이러스

바이러스 - 2606, 그래프 탐색, 실버3

---

🧐 알고리즘[접근방법]

1. 연결된 컴퓨터는 양방향 연결이다. 입력받은 연결된 컴퓨터를 배열에 넣어준다.
   ex) 1-2 연결이면 자동적으로 2-1 연결

2. 방문여부 배열 check 선언

3. 1번 컴퓨터 부터 방문하여 연결되어 있는 컴퓨터 탐색

---

👨‍💻 소스

• BFS Java

import java.util.*;

public class Main {

  public static int[][] map;
  public static boolean[] check;
  
  public static int count = 0;
  
  public static int BFS() {
    
    Queue<Integer> q = new LinkedList<Integer>();
    q.add(1);
    check[1] = true;
    
    while(!q.isEmpty()) {
      int n = q.poll();
      
      for(int i = 1 ; i < map[n].length ; i++) {
        if(map[n][i] == 1 && !check[i]) {
          q.add(i);
          check[i] = true;
          count++;
        }
      }
    }
    
    return count;
  }
  
  public static void main(String[] args){
    
    Scanner sc = new Scanner(System.in);
    
    int N = sc.nextInt(); // 컴퓨터 수
    int edges = sc.nextInt(); // 간선 수

    map = new int[N + 1][N + 1];
    check = new boolean[N + 1];
    
    
    for(int i = 0 ; i < edges ; i++) {
      int com1 = sc.nextInt();
      int com2 = sc.nextInt();
      
      map[com1][com2] = 1;
      map[com2][com1] = 1;
    }
    
    System.out.println(BFS());
    
    sc.close();
    
  }
  
  public static void printMap(int[][] map) {
    
    for(int i = 1 ; i < map.length ; i++) {
      for(int j = 1 ; j < map[i].length ; j++) {
        System.out.print(map[i][j] + "  ");
      }
      System.out.println();
    }
    System.out.println("====== printMap ======");
    
  }

}

• DFS Java

import java.util.*;

public class Main {

  public static int[][] map;
  public static boolean[] check;
  
  public static int count = 0;
  
  public static int DFS(int index) {
    
    check[index] = true;
    
    for(int i = 1 ; i < map[index].length ; i++) {
      if(map[index][i] == 1 && !check[i]) {
        count++;
        DFS(i);
      }
    }
    
    return count;
  }
  
  public static void main(String[] args){
    
    Scanner sc = new Scanner(System.in);
    
    int N = sc.nextInt(); // 컴퓨터 수
    int edges = sc.nextInt(); // 간선 수

    map = new int[N + 1][N + 1];
    check = new boolean[N + 1];
    
    
    for(int i = 0 ; i < edges ; i++) {
      int com1 = sc.nextInt();
      int com2 = sc.nextInt();
      
      map[com1][com2] = 1;
      map[com2][com1] = 1;
    }
    
    System.out.println(DFS(1));
    
    sc.close();
    
  }
  
  public static void printMap(int[][] map) {
    
    for(int i = 1 ; i < map.length ; i++) {
      for(int j = 1 ; j < map[i].length ; j++) {
        System.out.print(map[i][j] + "  ");
      }
      System.out.println();
    }
    System.out.println("====== printMap ======");
    
  }
  
}

---

🏅 결과

• BFS 결과
  

• DFS 결과
  

---

📖 관련 지식