[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) 같은 간선은 한 번만 주어진다.

 

출력

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

 

입출력

문제풀이

arr[] : 2차원 arraylist로 연결된 노드 데이터 저장

visit[] : 해당 노드에 방문 했는지 확인하는 배열

1. **방향이 없는 그래프라고 문제에 나와있기 때문에 연결돼 있는 노드데이터 모두를 저장해줘야 한다!!

      반례) 6 2
               1 3

               2 3   출력)4   // 노드 데이터 양방향으로 저장 하지 않으면 해당 반례에서 1,2가 연결 되지 않은 노드로 판단 된다.

 

2. 재귀사용해서 노드들을 방문해여 연결된 부분에 대해 탐색을 한다.

3. 연결된 부분에 대해 탐색이 끝났다면 연결요소 개수를 카운트 해준다.

4. 방문하지 않은 다른 노드의 연결 부분 탐색을 반복한다.

5. 모든 노드를 방문 했다면 연결요소 개수 출력

 

 

+

arraylist 2차원 배열 만들기

ArrayList<Integer>[] arr = new ArrayList[n + 1];

for (int i = 0; i <= n; i++) {
arr[i] = new ArrayList<Integer>();
}

 

코드

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class Main {
	static ArrayList<Integer>[] arr;  // arraylist 2차원배열 선언
	static boolean[] visit;
	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 e = Integer.parseInt(st.nextToken());
		int result =0;
		
		arr = new ArrayList[n + 1];
		visit = new boolean[n+1];
		
		
		for (int i = 0; i <= n; i++) {
			arr[i] = new ArrayList<Integer>();
		}
		for (int i = 0; i < e; i++) {
			st = new StringTokenizer(br.readLine());
			int n1 = Integer.parseInt(st.nextToken());
			int n2 = Integer.parseInt(st.nextToken());

			arr[n1].add(n2);
			arr[n2].add(n1);

		}
		for (int i = 1; i <= n; i++) {
			if(!visit[i]) {
				v(i);
				result ++;
			}
		}
		System.out.println(result);
	}

	public static void v(int a) {
		visit[a]=true;
		for(int i : arr[a]) {
			if(!visit[i]) v(i);
		}
	}
}