백준 11724 [연결 요소의 개수] - DFS/BFS

 

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

11724번: 연결 요소의 개수

 

연결 요소의 개수를 구하라는 뜻은 몇개의 덩어리로 이루어저있는지 구하라는 뜻이다.

아무것도 연결되지 않은 정점도 포함되어야한다.

DFS 또는 BFS 알고리즘을 이해했다면 앞서 말한 경우의 수는 자연스럽게 포함된다.

---

DFS 풀이

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
import java.util.Queue;
import java.util.LinkedList;

public class Main {
    static int [][]mapArr;
    static boolean []visitArr;
    
    public static void main(String[] args) throws Exception{ 
    	
    	BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
    	
    	StringTokenizer st = new StringTokenizer(br.readLine());
    	int N = Integer.parseInt(st.nextToken());
    	int M = Integer.parseInt(st.nextToken());
    	mapArr = new int[N+1][N+1];
    	visitArr = new boolean[N+1];
    	int cnt = 0;
    	
    	for(int i=0;i<M;i++) {
    	    st = new StringTokenizer(br.readLine());
    	    int a=Integer.parseInt(st.nextToken());
    	    int b=Integer.parseInt(st.nextToken());
    	    mapArr[a][b]=mapArr[b][a]=1;
    	}
    	
    	for(int i=1;i<N+1;i++) {
            //무한루프에 빠지지않기위해 방문여부 확인
    	    if(visitArr[i]==false) {
    	        dfs(i);
    	        cnt++;
    	    }
    	}
    	
    	System.out.print(cnt);
    }
    
    //Depth-First Search
    public static void dfs(int start) {
    	//방문한 노드
        visitArr[start]=true;
    	
        for(int i=1;i<mapArr.length;i++) {
            //mapArr[start][i]==1 두개의 정점이 연결되어있고
            //visitArr[i]==false 방문하지 않은 정점이라면
            if(mapArr[start][i]==1 && visitArr[i]==false) {
                dfs(i);
            }
        }
    }
}

 

---

BFS 풀이

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
import java.util.Queue;
import java.util.LinkedList;

public class Main {
    static int [][]mapArr;
    static boolean []visitArr;
    static Queue<Integer> queue;
    
    public static void main(String[] args) throws Exception{ 
    	
    	BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
    	
    	StringTokenizer st = new StringTokenizer(br.readLine());
    	int N = Integer.parseInt(st.nextToken());
    	int M = Integer.parseInt(st.nextToken());
    	mapArr = new int[N+1][N+1];
    	visitArr = new boolean[N+1];
        queue = new LinkedList<>();
    	int cnt = 0;
    	
    	for(int i=0;i<M;i++) {
    	    st = new StringTokenizer(br.readLine());
    	    int a=Integer.parseInt(st.nextToken());
    	    int b=Integer.parseInt(st.nextToken());
    	    mapArr[a][b]=mapArr[b][a]=1;
    	}
    	
    	for(int i=1;i<N+1;i++) {
            //무한루프에 빠지지않기위해 방문여부 확인
    	    if(visitArr[i]==false) {
    	        bfs(i);
    	        cnt++;
    	    }
    	}
    	
    	System.out.print(cnt);
    }
    
    //breath-First Search
    public static void bfs(int start) {
        //탐색을 시작할 정점
        queue.add(start);
        visitArr[start]=true;
    	
        //탐색을 시작한 정점으로부터 연결된 모든 정점 탐색
        while(!queue.isEmpty()) {
            int nIdx = queue.poll();
    		
            for(int i=1;i<mapArr.length;i++) {
                //mapArr[nIdx][i]==1 두 정점이 연결되어있고
                //visitArr[i]==false 방문하지 않은 정점이라면
                if(mapArr[nIdx][i]==1 && visitArr[i]==false) {
                    queue.add(i);
                    visitArr[i]=true;
                }
            }
        }
    }

}