[백준] 11724번 연결 요소의 개수

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

11724번: 연결 요소의 개수

---

[풀이 방법]

하나의 선으로 이어진 덩어리(?)가 몇 개 있는지 구하는 문제이다.

이 문제에서 방문 순서는 영향을 미치지 않기 때문에 dfs, bfs 상관없이 탐색을 하면된다!

 

1. 1~N개의 정점 중 아직 방문하지 않은 정점을 시작 정점으로 탐색 시작 

2. 한 번의 탐색이 끝나면 연결 요소의 개수 증가

    -> 한 번의 탐색이 끝났다는것은 하나의 선으로 이어진 정점들을 모두 방문했다는 의미

    -> 새로운 탐색을 시작해도 이미 방문한 정점은 방문하지 않을 것이기 때문에 방문 여부는 그래도 둔다

3. 더 이상 탐색을 시작할 정점이 없으면(for문을 모두 돌면) 연결 요소의 개수를 출력하고 종료

 

[풀이 코드_Java] DFS(Stack ) 사용

import java.util.HashMap;
import java.util.ArrayList;
import java.util.Scanner;
import java.util.Stack;

public class Main {
	
	static int N, M;
	static int cnt = 0;
	static boolean[] visited;
	static HashMap<Integer, ArrayList<Integer>> graph = new HashMap<>();
	
	
	public static void main(String[] args) {
		
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt();
		M = sc.nextInt();
		visited = new boolean[N + 1];
		
		for (int i = 0; i < M; i++) {  // 그래프 생성 
			int u = sc.nextInt(), v = sc.nextInt();
			
			if (graph.get(u) == null) graph.put(u, new ArrayList<Integer>());
			graph.get(u).add(v);
			
			if (graph.get(v) == null) graph.put(v, new ArrayList<Integer>());
			graph.get(v).add(u);
		}
		
		for (int n = 1; n < N + 1; n++) {  // 만약 방문하지 않은 노드라면 해당 노드를 시작점으로 탐색  
			if (!visited[n]) dfs(n);
		}
		
		System.out.println(cnt);
	}
	
	public static void dfs(int start) {
		Stack<Integer> stack = new Stack<>();
		stack.push(start);
		visited[start] = true;
		while (!stack.isEmpty()) {
			int n1 = stack.pop();
			
			if (graph.get(n1) == null)	continue;
			
			for (Integer n2: graph.get(n1)) {
				if (!visited[n2]) {
					stack.push(n2);
					visited[n2] = true;
				}
			}
		}
		cnt++;  // 한 번의 연결이 끝날때마다 연결요소의 개수 증가 
	}

}

 

 

[풀이 코드_Java] DFS(재귀 ) 사용

import java.util.HashMap;
import java.util.ArrayList;
import java.util.Scanner;

public class Main {
	
	static int N, M;
	static int cnt = 0;
	static boolean[] visited;
	static HashMap<Integer, ArrayList<Integer>> graph = new HashMap<>();
	
	
	public static void main(String[] args) {
		
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt();
		M = sc.nextInt();
		visited = new boolean[N + 1];
		
		for (int i = 0; i < M; i++) {  // 그래프 생성 
			int u = sc.nextInt(), v = sc.nextInt();
			
			if (graph.get(u) == null) graph.put(u, new ArrayList<Integer>());
			graph.get(u).add(v);
			
			if (graph.get(v) == null) graph.put(v, new ArrayList<Integer>());
			graph.get(v).add(u);
		}
		
		for (int n = 1; n < N + 1; n++) {  // 만약 방문하지 않은 노드라면 해당 노드를 시작점으로 탐색  
			if (!visited[n]) {
				dfs(n);
				cnt++;    // 한 번의 탐색이 끝날때마다 연결요소의개수 증가 
			}
		}
		
		System.out.println(cnt);
	}
	
	public static void dfs(int start) {
		if (visited[start]) return;
		visited[start] = true;
		
		if (graph.get(start) == null) return;
		
		for (Integer n: graph.get(start)) {
			if(!visited[n])	dfs(n);
		}
	}

}

 

 

[풀이 코드_Java] BFS 사용

import java.util.HashMap;
import java.util.ArrayList;
import java.util.Scanner;
import java.util.Queue;
import java.util.LinkedList;

public class baekjoon11724 {
	
	static int N, M;
	static int cnt = 0;
	static boolean[] visited;
	static HashMap<Integer, ArrayList<Integer>> graph = new HashMap<>();
	
	
	public static void main(String[] args) {
		
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt();
		M = sc.nextInt();
		visited = new boolean[N + 1];
		
		for (int i = 0; i < M; i++) {  // 그래프 생성 
			int u = sc.nextInt(), v = sc.nextInt();
			
			if (graph.get(u) == null) graph.put(u, new ArrayList<Integer>());
			graph.get(u).add(v);
			
			if (graph.get(v) == null) graph.put(v, new ArrayList<Integer>());
			graph.get(v).add(u);
		}
		
		for (int n = 1; n < N + 1; n++) {  // 만약 방문하지 않은 노드라면 해당 노드를 시작점으로 탐색  
			if (!visited[n])	bfs(n);
		}
		
		System.out.println(cnt);
	}
	
	public static void bfs(int start) {
		
		Queue<Integer> q = new LinkedList<>();
		q.add(start);
		visited[start] = true;
		while (!q.isEmpty()) {
			int n1 = q.poll();
			
			if (graph.get(n1) == null)	continue;
			
			for (Integer n2: graph.get(n1)) {
				if (!visited[n2]) {
					q.add(n2);
					visited[n2] = true;
				}
			}
		}
		cnt++;     // 한 번의 탐색이 끝날때 마다 연결 요소의 개수 증가  
		
	}

}