연결 요소 개수(11724번)

• 티어 : Sliver 2
• 정답여부 : 정답
• 알고리즘 유형 : 그래프 이론, 그래프 탐색,너비 우선 탐색,깊이 우선 탐색
• 시간 제한 : 3초

💡문제

방향 없는 그래프가 주어졌을 때, 연결 요소 (Connected Component)의 개수를 구하는 프로그램을 작성하시오.

💡입력

첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주어진다.

💡출력

첫째 줄에 연결 요소의 개수를 출력한다.

💡예제 입력 1

6 5
1 2
2 5
5 1
3 4
4 6

💡예제 출력 1

2

💡예제 입력 2

6 8
1 2
2 5
5 1
3 4
4 6
5 4
2 4
2 3

💡예제 출력 2

1

💡문제요약

연결된 노드의 개수를 구하면 되는 문제

💡알고리즘 설계

• N : 정점의 개수
• M : 간선의 개수
• u, v: 간선으로 이루어진 정점들
• arr : 그래프
• visit: 노드를 방문확인용

1. N과 M을 입력받음
2. 각 연결되는 노드 u, v를 입력받음
3. 각 입력받은 노드는 연결되어 있다는 1로 표시
4. 각 노드끼리 연결되어 있는 팀을 찾기 위해 DFS , BFS 실행

• DFS
  1. 시작점을 받아오고 방문했던 노드로 표시
  2. 인접한 노드를 찾도록 재귀함수 실행
• BFS
  1. 시작점 노드를 받아 que에 추가하여 방문했던 노시 표시
  2. temp에 시작점 노드를 꺼내주고 인접한 노드를 찾아줌 찾게 된다면 큐에 추가 해주고 방문했던 노드로 표시
  3. 큐가 비어있다면 노드는 없는것으로 반복문 종료

💡작성코드

• Java

import java.util.*;
import java.io.*;
public class Main {
	static int N , M;
	static int u , v;
	static int[][] arr;
	static boolean []visit;
	static int cnt;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		arr = new int[N+1][N+1];
		visit = new boolean[N+1];
		for(int i = 0; i < M; i++) {
			StringTokenizer sts = new StringTokenizer(br.readLine());
			u = Integer.parseInt(sts.nextToken());
			v = Integer.parseInt(sts.nextToken());
			arr[u][v] = arr[v][u] = 1;
		}
		for(int i = 1; i <= N; i++) {
			if(!visit[i]) {
				dfs(i);
				cnt++;
			}
		}
		System.out.println(cnt);	
	}
	public static void dfs(int start) {
		visit[start] = true;
		for(int i = 1; i <= N; i++) {
			if(arr[start][i] == 1 && !visit[i]) {
				dfs(i);
			}
		}	
	}
}

💡시간복잡도

O(M + N^2)

💡틀린 이유 or 수정할 부분

저번 DFS , BFS 구현 문제와 같아서 BFS로도 풀어봤다. 어려운건 없었다.

💡틀린 부분 수정 or 다른풀이

• Java

import java.io.*;
import java.util.*;
public class Main {
	static int N , M;
	static int u , v;
	static int[][] arr;
	static boolean []visit;
	static int cnt;
	static Queue<Integer>que = new LinkedList<>();
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		arr = new int[N+1][N+1];
		visit = new boolean[N+1];
		for(int i = 0; i < M; i++) {
			StringTokenizer sts = new StringTokenizer(br.readLine());
			u = Integer.parseInt(sts.nextToken());
			v = Integer.parseInt(sts.nextToken());
			arr[u][v] = arr[v][u] = 1;
		}
		for(int i =1; i <= N; i++) {
			if(!visit[i]) {
				bfs(i);
				cnt++;
			}
		}
		System.out.println(cnt);
	}
	public static void bfs(int start) {
		que.offer(start);
		visit[start] = true;
		while(!que.isEmpty()) {
			int temp = que.poll();
			for(int i = 1; i <=N; i++) {
				if(arr[temp][i] == 1 && !visit[i]) {
					que.offer(i);
					visit[i] = true;
				}
			}
		}	
	}
}

💡느낀점 or 기억할 정보

이제까지는 입력받은 수가 x, y 위치라 위치를 찾는 구조라서 이해하기 쉬웠는데 노드로 생각을 해버리면 뭔가 무방향 그래프라서 이해하기가 조금 벅차지만 그림을 그리면서 하나하나 조건을 따지며 재귀함수 , 큐를 직접 구현해보면서 로그를 찍어보니 조금은 코드가 동작을 어떻게 되는지 알거같다.