[B0J]연결 요소의 개수(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. 큐가 비어있다면 노드는 없는것으로 반복문 종료

💡시간복잡도

• O(M + N^2)

💡코드

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);
			}
		}
		
	}

}

💡 틀린 이유

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

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

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 위치라 위치를 찾는 구조라서 이해하기 쉬웠는데 노드를 무방향 그래프로 생각을 하면 이해하기가 생각보다 힘들다. 그리고 내가 DFS, BFS 코드를 이해보다는 외운감이 있는거 같다. 그래서 그림을 그리면서 하나하나 조건을 따지며 재귀함수 , 큐를 직접 구현해보면서 로그를 찍어보니 코드가 어떻게 동작하는지 조금 더 이해하기 수월해진거 같다.