연결 요소의 개수(11724)

연결 요소의 개수(11724)

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

public class Main {
  
  static boolean[][] node;
  static boolean[] visited;
  static int n;
  
  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    StringBuilder sb = new StringBuilder();
    
    StringTokenizer st =  new StringTokenizer(br.readLine());
    
    n = Integer.parseInt(st.nextToken()); 
    int m = Integer.parseInt(st.nextToken());
    
    node = new boolean[n+1][n+1];
    visited = new boolean[n+1];
    
    for(int i = 0; i < m ; i++) {
      st = new StringTokenizer(br.readLine());
      int a = Integer.parseInt(st.nextToken()), b= Integer.parseInt(st.nextToken());
      
      node[a][b] = true;
      node[b][a] = true;
    }
    
    int cnt = 0;
    
    for(int i = 1; i <= n; i++) {
      if(!visited[i]) cnt += check(i);
    }
    
    sb.append(cnt);
    
    bw.write(sb.toString());
    bw.flush();
    bw.close();
    br.close();
  }
  
  public static int check(int start) {
    Deque<Integer> dq = new ArrayDeque<>();
    
    dq.offerFirst(start);
    
    while(!dq.isEmpty()) {
      int num = dq.pollFirst();

      if(visited[num]) continue;
      
      visited[num] = true;
      
      for(int i = 1; i <= n; i++) {
        if(node[num][i] && !visited[i]) {
          dq.offerFirst(i);
        }
      }
    }
    
    return 1;
  }
}

풀이과정

1. DFS를 사용하고, stack을 사용하여 구현하는 방향으로 접근하였다.
2. DFS로 접근하며 방문을 기록하고, 시작점과 연결된 모든 노드를 순회하였을 때 1을 반환하였다. 모든 연결노드를 순회하였고, 그 덩어리가 1개 나왔다는 의미였다.
3. 메인 메소드에서 for문을 이용하여 매개변수를 넘겨주었는데, 이미 방문한 노드는 check() 메소드를 다시 호출하면 안된다.
4. 아직 방문하지 않은 노드가 있다면 이 노드는 다른 덩어리에 속하는 노드이기 때문에 다시 DFS 탐색을 진행한다.

- 성공
- 메모리 : 126812 KB
- 시간 : 564 ms

보안점