백준 11724 - 연결 요소의 개수 (JAVA 자바)

백준 11724 - 연결 요소의 개수 (JAVA 자바)

 

www.acmicpc.net/problem/11724

11724번: 연결 요소의 개수

 

기본적인 DFS 문제입니다.

아래 주의사항들을 참고하셔서 코드 짜시면 됩니다. 

 

1. 중간에 간선이 끊겨있을 수 있으므로, 방문하지 않은 지점에서 DFS가 다시 시작할 수 있도록 해줍니다.

   (for문 안에 dfs를 배치할 것)

2. DFS가 한번 끝날때마다 cnt 변수를 +1 해준 뒤, 마지막에 cnt 변수만 출력해주면 정답이 됩니다. 

3. 간선은 방향성이 없으므로, 양방향으로 갈 수 있도록 설정해줍니다. 

 

 

 

 

import java.util.*;
 
public class Main {
    
    static int spots, nodes, cnt;
    static boolean visits[];
    static boolean map[][];
 
    public static void main(String[] args) {
 
        Scanner sc = new Scanner(System.in);
        
        spots = sc.nextInt();
        nodes = sc.nextInt();
        visits = new boolean[spots+1];
        map = new boolean[spots+1][spots+1];
        cnt = 0;
        for (int i=1; i<=nodes; i++) {
            int tmp1 = sc.nextInt();
            int tmp2 = sc.nextInt();
            
            map[tmp1][tmp2] = true;
            map[tmp2][tmp1] = true;
            
        }
        
        for(int i=1; i<=spots; i++) {
            if (!visits[i]) {
                dfs(i);
                cnt++;
            }
        }
        
        System.out.println(cnt);
        
    }
    
    private static void dfs(int start) {
        visits[start]=true;
        
        for(int i=1; i<=spots; i++) {
            if (map[start][i] && !visits[i]) {
                dfs(i);
            }
        }
    }
}