백준 11724 연결 요소의 개수(Java)

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

11724번: 연결 요소의 개수

---

 

해석 및 팁

 

---

 

이 문제는 dfs로 풀면 되는 문제입니다. visit 배열을 만들어서 처음부터 돌면서 방문하지 않은 값이 있다면 dfs 함수를 실행하고 count++을 해주면 됩니다.

 

---

 

Java 코드

 

---

import java.util.Scanner;

public class Main {

  static int count;
  static int n;
  static boolean[][] arr;
  static boolean[] visit;

  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);

    count = 0;
    n = sc.nextInt();
    int m = sc.nextInt();
    
    arr = new boolean[n + 1][n + 1];
    visit = new boolean[n + 1];

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

    for(int i = 1; i <= n; i++) {
      if(visit[i] == false) {
        count++;
        dfs(i);
      }
    }

    System.out.println(count);
  }

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