[JAVA] 11724. 연결 요소의 개수

문제

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

입력

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

출력

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

Code

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 BOJ_11724 {
	
	public static int N, M;
	public static int[][] graph; // 인접행렬
	static boolean[] visited; // 방문여부
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		
		st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken()); // 정점의 개수
		M = Integer.parseInt(st.nextToken()); // 간선의 개수
		graph = new int[N][N];
		visited = new boolean[N];
		int answer = 0;
		
		for (int i=0; i<M; i++) {
			st = new StringTokenizer(br.readLine());
			int u = Integer.parseInt(st.nextToken()) - 1; // 0부터 시작하기 위함
			int v = Integer.parseInt(st.nextToken()) - 1;
			graph[u][v] = 1; // 연결 상태
			graph[v][u] = 1; // 연결 상태
		}
		
		for (int i=0; i<N; i++) {
			if(!visited[i]) {
				bfs(i);
				answer++;
			}
		}
		System.out.println(answer);
	}
	
	public static void bfs(int node) {
		Queue<Integer> que = new LinkedList<Integer>();
		que.add(node);
		visited[node] = true;
		
		while(!que.isEmpty()) {
			int now = que.poll(); // 기준
			for (int i=0; i<N; i++) { // 연결되어있는 모든 노드 확인
				if (graph[now][i] == 1 && !visited[i]) { // 연결되었고 방문한 적이 없다면
					que.add(i); // 큐에 추가
					visited[i] = true; // 방문처리
				}
			}
		}
	}
}

Today I Leaned

인접행렬을 사용해서 풀었더니 오랜만이라서 조금 헤맨감이 있었다. 인접 리스트를 사용하는게 더 좋을 것 같다.
https://freestrokes.tistory.com/87

Java 인접행렬과 인접리스트를 이용하여 그래프 구현하기

그리고 bfs를 사용했지만 dfs, 플로이드와샬까지 다양한 풀이 방법이 있었다. 나중에 참고해서 풀이방법을 익히는 것도 좋을 것 같다. 여러가지를 연습할 수 있는 기본문제 느낌?
https://velog.io/@lifeisbeautiful/%EB%B0%B1%EC%A4%80-11724%EB%B2%88-%EC%97%B0%EA%B2%B0-%EC%9A%94%EC%86%8C%EC%9D%98-%EA%B0%9C%EC%88%98-Java

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