[백준-11724번 자바/java] 연결 요소의 개수 _디버깅의 눈물
https://www.acmicpc.net/problem/11724
11724번: 연결 요소의 개수
첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주
www.acmicpc.net
연결 요소의 개수 성공
| 3 초 | 512 MB | 76793 | 35162 | 23181 | 42.913% |
문제
방향 없는 그래프가 주어졌을 때, 연결 요소 (Connected Component)의 개수를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주어진다.
출력
첫째 줄에 연결 요소의 개수를 출력한다.
예제 입력 1 복사
6 5
1 2
2 5
5 1
3 4
4 6
예제 출력 1 복사
2
예제 입력 2 복사
6 8
1 2
2 5
5 1
3 4
4 6
5 4
2 4
2 3
예제 출력 2 복사
1
체크 포인트
1. 깊이 우선 탐색(DFS) 문제
-BFS로도 풀이가 가능하지만, 모든 정점을 탐색해나가는 DFS문제로 접근했다.
2. 정점 간 양방향 처리
// 지도 배열 정점 정보 입력
for(int i=1; i<=M; i++){
st = new StringTokenizer(br.readLine(), " ");
int u = Integer.parseInt(st.nextToken());
int v = Integer.parseInt(st.nextToken());
// 양방향 처리를 통해 정점 간 연결 확인
map[u][v] = map[v][u] = 1;
}
-정점과 간선의 정보를 담고 있는 지도 배열의 값을 입력 받을 때,
-정점 간 양방향 처리를 위해, map[u][v] = map[v][u] = 1 로 표시해주었다.
예를 들어, 정점의 개수(N)이 3이고, 간선의 수(M)가 2이고
해당 간선의 양끝점으로 (1,3), (2,3)이 주어질 때,
양방향 처리를 통해 (1,3)과 (3,2)로서 '3'을 통해 서로 연결되어 있음을 나타낼 수 있기 때문이다.
그 결과 총 연결요소의 개수는 1개로 된다.
양방향 처리가 없다면 (1,3)과 (2,3)이 연결되어 있지 않은 별개의 정점으로 간주되기 때문에
총 연결요소의 개수는 2로 출력될 것이다.
3. 연결 요소의 카운팅 지점
-DFS 탐색 중인 정점과, 연결된 간선 관계의 모든 정점 그룹을, 하나의 연결요소로 카운팅해야 한다.
-예제 1번을 예를 들면,
(1,2), (2,5), (5,1) 은 연결된 하나의 연결요소이다.
1번 정점 탐색을 통해 2번과 5번 정점이 모두 연결된 것을 확인하고, 방문처리를 함으로써,
2번과 5번은 추가적인 탐색이 필요없게 된다.(1번 탐색 과정에서 이미 모두 파악됨)
// 1번 정점부터 모든 정점을 DFS로 탐색 시작
for(int i=1; i<=N; i++){
if(visited[i]==false){
DFS(i);
// 연결 요소 개수 추가
count++;
}
}
이 모든 과정이 하나의 연결요소이기 때문에, 해당 DFS가 모두 끝난 후 count++을 해주는 것이다.
풀이
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
// 정점의 개수 N, 간선의 개수 M
static int N, M;
// 연결 요소의 개수
static int count;
// 정점들이 존재하는 지도 배열
static int[][] map;
// 해당 정점의 방문 여부를 나타내는 배열
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(), " ");
// 정점의 개수
N = Integer.parseInt(st.nextToken());
// 간선의 개수
M = Integer.parseInt(st.nextToken());
// 배열 초기화
map = new int [N+1][N+1];
// 정점의 방문여부 배열 초기화
visited = new boolean[N+1];
// 지도 배열 정점 정보 입력
for(int i=1; i<=M; i++){
st = new StringTokenizer(br.readLine(), " ");
int u = Integer.parseInt(st.nextToken());
int v = Integer.parseInt(st.nextToken());
// 양방향 처리를 통해 정점 간 연결 확인
map[u][v] = map[v][u] = 1;
}
/*
for(int i=1; i<=N; i++){
for(int j=1; j<=N; j++){
if(j==N){
System.out.println(map[i][j] + " ");
}
else{
System.out.print(map[i][j] + " ");
}
}
}
*/
// 1번 정점부터 모든 정점을 DFS로 탐색 시작
for(int i=1; i<=N; i++){
if(visited[i]==false){
DFS(i);
// 연결 요소 개수 추가
count++;
}
}
System.out.println(count);
}
static void DFS(int start) {
// 해당 정점 방문 처리
visited[start] = true;
for(int i=1; i<=N; i++){
// (start,i)이 정점이고, i에 방문한 적이 없다면
// 정점 i에 방문한 적이 없는 경우,
if(map[start][i] == 1 && !visited[i]){
// 정점 i DFS 탐색 시작
DFS(i);
}
}
}
} // end of Main