[백준/BOJ] 11724번 : 연결 요소의 개수 (JAVA / 자바)

안녕하세요~ 코딩하는 코알못 코메인입니다.

 

 

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

11724번: 연결 요소의 개수

---

- 문제 -

 

난이도 실버 2 문제이다.

자바에서 입력방식은 scanner와 bufferedreader가 있다.

자바를 초반에 접하면 처음에 배우는 입력은 scanner이다. scanner가 bufferedreader보다 편하지만 속도가 느리다.

bufferedreader는 무조건 문자열로 받아오기때문에 정수형이나 실수형 변수에 저장하기 위해서는 입력과 형변환을 해줘야한다.

더 자세한 내용은 아래 글 참고 하면 좋다.

https://comain.tistory.com/3

(JAVA / 자바) Scanner 와 Bufferedreader

 

풀이 방법

DFS를 사용해 풀어보겠다.

연결 요소의 개수를 구하는 것인데 이 연결 요소가 무엇인지 간략하게 짚고 가자.

DFS와 BFS를 공부하면 나오는 것이 노드와 간선이다. 쉽게 간선을 연결이라 하겠다.

노드끼리 연결이 되어있으면 그 연결을 따라서 탐색하는 것이 DFS와 BFS인데, 어떤 노드들은 다른 노드들과 아무런 연결이 안되어있거나, 따로 자기들끼리만 연결이 되어있다. 이렇게 연결이 따로 노는 쉽게 말해 그룹들의 개수를 말하는 것이다.

예를 들면 5개의 정점이 있고, 간선이 3개일때, 1과 2, 2와 3, 4와 5가 간선으로 연결되어있다면 1 2 3이 서로 연결되어있고, 4 5가 서로 연결되어있다. 그렇게되면 1 2 3, 4 5그룹이 생기는 것이고, 이 그룹의 개수를 출력한다. 두개이지 2를 출력하면 된다.

 

DFS의 방식을 사용하는데, 이 넓이, 깊이 우선 탐색이란건 결국 간선이 존재하면 전부다 읽어낼 수 있다. 보통 시작점을 짚어주면 거기서 시작해서 연결되어있는 모든 정점을 읽는데, 위에서 예를 든 것에 시작점을 1로 잡으면 1 2 3만 나오게 된다. 그렇게 되면 4와 5는 아예 확인도 못하니 1~5까지 전부다 시작점에 넣고, 간선으로 연결되어있다면 그룹에 집어넣고, 그룹의 개수를 세주면 된다.

주의할 점은 간선이 연결되어있지 않은 경우인데, 말그대로 정점 혼자서만 열결 없이 덩그러니 있는 경우다. 이런 경우도 그룹에 넣어줘야하는데, DFS, BFS의 기본은 연결이 되어있는 것을 탐색하기때문에 연결이 아무데도 되어있지 않은 정점은 취급을 하지 않게된다. 그렇기때문에 조건을 하나 추가해준다. 조건을 말하기 전에 탐색의 기본은 1~정점의 최댓값 까지 현재 확인중인 노드의 연결된 값이 나올때까지 작은수부터 큰 수까지 확인한다. 현재 노드가 연결된 값이 하나도 없다면 큰수까지 갈 것이고, 그렇다면 정점의 개수만큼 반복을 하게 되는 것이다. 연결이 안되어있는 정점을 확인하기 위한 정수형 변수를 하나 만들어주고, 연결이 안된 값이 확인될때마다 +1을 해준다. 그렇게 현재 노드의 탐색이 끝났을때, 변수의 값이 정점의 개수와 같다면 그것은 아무것도 연결이 안된 정점이니, 그룹의 개수에 추가를 해준다.

 

코드를 보자.

---

-풀이-

 

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

public class Main {
		static int N;
		static int[][] graph = new int[1001][1001];
		static boolean[] visit = new boolean[500000];
		//그룹에 정점이 들어왔는지 확인하기 위한 변수
		static int CC = 0;
		//연결이 없는 노드(정점)을 파악하기 위한 변수
		static int count = 0;
		
	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());
		int M = Integer.parseInt(st.nextToken());
		//출력값을 저장할 변수
		int result = 0;
		
		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;
		}
		
		for(int i = 1; i <= N; i++) {
			DFS(i);
			//CC가 0이 아니라면 그룹에 들어온 노드가 있다는 뜻이니,
			//그룹의 개수(출력 값 변수)에 +1을 해준다.
			if(CC != 0) {
				result++;
			}
			//count가 정점의 개수와 같다면 연결이 없는 정점이기에
			//그룹의 개수에 +1을 해준다.
			if(count == N) {
				result++;
			}
			//확인이 끝났으면 CC와 count는 0으로 초기화
			CC = 0;
			count = 0;
		}
		System.out.println(result);
	}
	
	//탐색 메소드
	public static void DFS(int node) {
		visit[node] = true;
		
		for(int i = 1; i <= N; i++) {
			if(!visit[i] && graph[node][i] == 1) {
				DFS(i);
				CC++;
				count = 0;
			}
			//현재 정점과 연결된 정점이 없다면 count에 +1을 해준다.
			if(graph[node][i] == 0) {
				count++;
			}
		}
	}

}

---

-결과-

 

---

아직 코딩 공부가 부족한 필자라 설명과 풀이 방법이 많이 미흡할 수 있다. 코딩 고수분들은 보시고 문제점이 있다면 댓글로 말해주시면 감사한 마음으로 참고 수정 하겠습니다.