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

백준 11724

시간 제한메모리 제한제출정답맞힌 사람정답 비율

 

3 초

512 MB

135001

60950

40026

42.030%

문제

방향 없는 그래프가 주어졌을 때, 연결 요소 (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 를 통해 구현한다.
• 한번 방문한 배열은 다시 방문하지 않는다.
• 위 노드는 양방향 이므로 1->2 , 2->1 다 가능하다.

 

2️⃣ 요구 조건 구현하기

• Bufferedreader 생성

 

 

3️⃣ 슈도 코드

n(노드 개수) m(엣지 개수)
A(그래프 데이터 저장 인접 리스트)
visited(방문 기록 저장 배열)

for(n의 개수만큼 반복하기) {
	A 인접 리스트의 각 ArrayList 초기화하기
}

For(m의 개수만큼 반복하기) {
	A 인접 리스트에 그래프 데이터 저장하기
}

for(n의 개수 만큼 반복하기) {
	if(방문하지 않은 노드가 있으면) {
    	연결 요소 개수++;
        DFS 실행하기
    }
}

// DFS 구현하기
DFS {
	if(현재 노드 == 방문 노드) return; // 더 이상 방문하지 않는다
    visited 배열에 현재 노드 방문 기록하기
    현재 노드의 연결 노드 중 방문하지 않는 노드로 DFS 실행하기(재귀 함수 형태
}

 

DFS 를 푸는 방법은 Stack 자료구조 또는 재귀 함수 두가지를 이용할 수 있습니다.

Stack - FILO(First in Last out)

 

 

4️⃣ 코드 작성

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

public class B11724 {
	static boolean visited[]; // 방문 배열
	static ArrayList<Integer>[] A;

	public static void main (String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(bf.readLine());

		int n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());

		visited = new boolean[n+1];
		A = new ArrayList[n+1];

		for (int i = 1; i <n+1 ; i++) {
			A[i] = new ArrayList<Integer>(); // A 인접 리스트의 각 ArrayList 초기화하기
		}

		for (int i = 0; i <m ; i++) {
			st = new StringTokenizer(bf.readLine());
			int start = Integer.parseInt(st.nextToken());
			int end = Integer.parseInt(st.nextToken());

			// 양방향 설정하기
			A[start].add(end);
			A[end].add(start);
		}

		int count = 0;
		for (int i = 1; i <n+1 ; i++) {
			if(!visited[i]) {
				count++;
				DFS(i);
			}
		}
		System.out.println(count);
	}
	public static void DFS(int v) {
		if(visited[v]) {
			return;
		}
		visited[v] = true;
		// 현재 연결 노드 중 방문하지 않은 노드를 찾아야 한다.
		for (int i : A[v]) {
			if(!visited[i]) {
				DFS(i); // 아직 탐색하지 않은 노드가 있다면 현재를 기준으로 다시 DFS 를 구현해줘라
			}
		}
	}

}

 

5️⃣ 핵심 파악하기

1. 시작점 설정: 탐색을 시작할 정점을 정한다.
2. 방문 표시: 현재 정점을 방문했다고 표시한다.
3. 재귀 호출: 인접한 정점들 중 방문하지 않은 정점을 재귀적으로 방문한다.
4. 탐색 종료: 더 이상 방문할 정점이 없으면 재귀 호출을 종료한다.

 

위 특징을 알아야지 문제를 풀기가 수월 합니다

그래프의 모든 노드를 깊이 우선으로 탐색하는게 DFS 이고 DFS는 스택 자료 구조를 사용하여 구현할 수도 있다.