[BOJ] 백준 11724. 연결요소 개수 구하기

https://www.acmicpc.net/problem/11724

시간제한: 3초

레벨: 실2

연결요소?

→ 에지로 연결된 노드의 집합으로, 한 번의 DFS가 끝날 때까지 탐색한 노드의 집합을 하나의 연결 요소로 판단할 수 있음

풀이

선언, 입출력

static ArrayList<Integer>[] A;
	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());

주어진 정수만큼의 크기를 가진 노드를 초기화, 값 받아오기

A = new ArrayList[n+1]; // n+1 만큼의 배열을 가진 배열리스트 A
		visited = new boolean[n+1];
		
		// 주어진 정수만큼의 노드를 초기화시킨다
		for (int i = 1; i < n+1; i++) {
			A[i] = new ArrayList<Integer>();
		}
		
		//연결요소는 양방향에지이므로 값을 받아들이면 양쪽에 이를 더해준다
		//모든 관계를 반복 
		for (int i = 0; i < m; i++) {
			st = new StringTokenizer(br.readLine());
			int x = Integer.parseInt(st.nextToken());
			int y = Integer.parseInt(st.nextToken());
			
			A[x].add(y);
			A[y].add(x);
		}

연결요소의 개수를 구하기 위해 탐색 수행! 한번의 탐색이 끝날때까지 탐색한 노드의 집합이 연결요소 이므로 탐색이 끝나면 카운트를 세준다.

int count = 0;
		
		//모두 방문할때까지 반복, 방문했다면 루프 빠져나오기 
		for (int i = 1; i < n+1; i++) {
			if(!visited[i]) { // 방문하지 않았다면 
				count ++;
				DFS(i); // 너비우선탐색을 실행
			}
		} //end
		
		System.out.println(count);
	}
	
	
	// DFS로직
	static void DFS(int v) {
		if(visited[v]) { //방문했으면 나오기
			return; 
		}
		visited[v] = true; // 방문했다고 표시하기 
		for(int i: A[v]) { // 배열안에 있는 것을 차례로 순회 
			if(visited[i] == false) { // 방문안했으면 방문
				DFS(i);
			}
		}
	}

전체코드

/**
 * 백준 연결 요소의 개수 구하기 DFS
 * 
 */

package b11724;

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

public class Main {
	
	// 사용할 배열리스트, 방문한지 체크할  boolean 선언
	static ArrayList<Integer>[] A;
	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());
		
		A = new ArrayList[n+1]; // n+1 만큼의 배열을 가진 배열리스트 A
		visited = new boolean[n+1];
		
		// 주어진 정수만큼의 노드를 초기화시킨다
		for (int i = 1; i < n+1; i++) {
			A[i] = new ArrayList<Integer>();
		}
		
		//연결요소는 양방향에지이므로 값을 받아들이면 양쪽에 이를 더해준다
		//모든 관계를 반복 
		for (int i = 0; i < m; i++) {
			st = new StringTokenizer(br.readLine());
			int x = Integer.parseInt(st.nextToken());
			int y = Integer.parseInt(st.nextToken());
			
			A[x].add(y);
			A[y].add(x);
		}
		
		int count = 0;
		
		//모두 방문할때까지 반복, 방문했다면 루프 빠져나오기 
		for (int i = 1; i < n+1; i++) {
			if(!visited[i]) { // 방문하지 않았다면 
				count ++;
				DFS(i); // 너비우선탐색을 실행
			}
		} //end
		
		System.out.println(count);
	}
	
	
	// DFS로직
	static void DFS(int v) {
		if(visited[v]) { //방문했으면 나오기
			return; 
		}
		visited[v] = true; // 방문했다고 표시하기 
		for(int i: A[v]) { // 배열안에 있는 것을 차례로 순회 
			if(visited[i] == false) { // 방문안했으면 방문
				DFS(i);
			}
		}
	}
	
	
}