[Silver II] 연결 요소의 개수 - 11724
성능 요약
메모리: 118528 KB, 시간: 484 ms
분류
그래프 이론, 그래프 탐색, 너비 우선 탐색, 깊이 우선 탐색
제출 일자
2023년 11월 30일 10:00:16
문제 설명
방향 없는 그래프가 주어졌을 때, 연결 요소 (Connected Component)의 개수를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주어진다.
출력
첫째 줄에 연결 요소의 개수를 출력한다.
풀이 과정
1. main 함수에서 방문하지 않은 노드가 있다면 Result에 ++ 후 bfs메서드 호출
2. bfs 할 때 방문 할 수 있는 노드는 전부 true 처리 -> 처리 된 곳끼리는 연결 요소
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class Main {
static int[][] graph;
static boolean[] visited;
public static void main(String[] args) throws IOException {
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());
graph = new int[n+1][n+1];
visited = new boolean[n+1];
for(int i = 0; i < m; i++){
st = new StringTokenizer(br.readLine());
int u = Integer.parseInt(st.nextToken());
int v = Integer.parseInt(st.nextToken());
graph[u][v] = graph[v][u] = 1;
}
int result = 0;
for(int i = 1; i <= n; i++){
if(!visited[i]){
result++;
// 연결된 노드를 방문처리
bfs(i);
}
}
System.out.println(result);
}
private static void bfs(int start) {
// start 노드 방문
visited[start] = true;
Queue<Integer> q = new LinkedList<>();
q.offer(start);
// q가 빈다는건 연결된 요소가 없다는 것
while (!q.isEmpty()) {
// 현재 요소를 빼줌
int cur = q.poll();
// 현재 요소와 연결된 노드를 확인
for(int i = 1; i< graph[cur].length; i++){
// 연결된 곳 중 방문하지 않은 곳이 있을 때
if(graph[cur][i] == 1 && !visited[i]){
// 방문 처리 후 큐에 삽입
visited[i] = true;
q.offer(i);
}
}
}
}
}
'알고리즘 - Baekjoon > Silver' 카테고리의 다른 글
[백준] 10451번 : 순열 사이클 Silver 3(실버 3) - JAVA[자바] (1) | 2023.12.10 |
---|---|
[백준] 10819번 : 차이를 최대로 Silver2(실버2) - JAVA[자바] (0) | 2023.12.01 |
[백준] 11576번 : Base Conversion Silver5(실버5) - JAVA[자바] (0) | 2023.11.29 |
[백준] 1992번 : 쿼드트리 Silver1(실버1) - JAVA[자바] (1) | 2023.11.28 |
[백준] 1780번 : 종이의 개수 Silver2(실버2) - JAVA[자바] (1) | 2023.11.27 |