[백준] 11724번 : 연결 요소의 개수

연결 요소의 개수 성공

 

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

3 초

512 MB

155372

70478

46091

42.203%

문제

방향 없는 그래프가 주어졌을 때, 연결 요소 (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

 

 

 

package 문제11724연결요소의개수;

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.Stack;
import java.util.StringTokenizer;

public class Main {
	static List<Integer>[] arr;
	static int N;
	static boolean[] visited;

	public static void main(String[] args) throws IOException {
		System.setIn(new FileInputStream("res/문제11724연결요소의개수.txt"));
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String s = br.readLine();
		StringTokenizer st = new StringTokenizer(s);
		N = Integer.parseInt(st.nextToken()); // 1<=N<=1000
		int M = Integer.parseInt(st.nextToken()); // 0<=M<=N(N-1)/2 (하나도 없거나 전부 연결하거나 가능)
		arr = new ArrayList[N + 1];
		visited = new boolean[N+1];
		for (int i = 0; i <= N; i++) {
			arr[i] = new ArrayList<>();
		}
		for (int i = 0; i < M; i++) {
			s = br.readLine();
			st = new StringTokenizer(s);
			int A = Integer.parseInt(st.nextToken());
			int B = Integer.parseInt(st.nextToken());
			arr[A].add(B);
			arr[B].add(A);
		} // 입력
		int count = 0;
		for (int i =1; i<=N; i++) {
			if (visited[i]!=true && !arr[i].isEmpty()) {
				dfs(i);
				count++;
			}
			else if (visited[i]!=true && arr[i].isEmpty()) {
				count++; // 어느 노선에도 연결되지 않은 경우
			}
		}
		
		System.out.println(count);
		

	}
	public static void dfs(int A) {
		Stack<Integer> stack = new Stack<>();
		stack.add(A);
		visited[A] = true;
		while(!stack.isEmpty()) {
			int num = stack.pop();
			for (int n : arr[num]) { // 스택에 집어 넣고 방문 처리
				if (visited[n] !=true) { // 방문한 적이 없다면
					stack.add(n);
					visited[n] = true;					
				}
			}
		}
		return;
	}

}

 

 

 

🔴 틀린 부분 요약 & 해결 방법 (2번이 찐 틀린 이유)

1️⃣ DFS를 구현한다고 했지만, BFS처럼 구현됨

• 문제점: Queue → Stack으로 바꿨지만, DFS의 핵심인 시작 노드 방문 체크를 안 함
• 해결 방법:
  • stack.add(A); (초기 노드부터 스택에 넣기)
  • visited[A] = true; (초기 노드 방문 처리하기)

2️⃣ 연결 요소 개수를 세는 조건이 잘못됨

• 문제점: !arr[i].isEmpty() 조건을 걸어서 고립된 노드(간선 없는 노드)를 체크하지 못함
• 해결 방법:
  • if (!visited[i]) { dfs(i); count++; }
  • 그냥 방문하지 않은 노드만 체크하면 됨!

3️⃣ DFS 호출 전에 visited 체크를 실수함

• 문제점:
  java

  복사편집

  if (visited[i] != true && !arr[i].isEmpty()) { dfs(i); count++; } else if (visited[i] != true && !arr[i].isEmpty()) { count++; }
  • !arr[i].isEmpty()를 체크하는 바람에 고립된 노드를 세지 못함.
  • else if 조건이 잘못됨 (!arr[i].isEmpty() → arr[i].isEmpty())
• 해결 방법:
  • if (!visited[i]) { dfs(i); count++; } 이 한 줄로 해결됨!

---

✅ 앞으로 실수 안 하려면 꼭 기억할 것!

✔ DFS/BFS를 구현할 때 "시작 노드 방문 체크" 필수!
✔ 연결 요소 개수 셀 때는 "방문 여부만 확인"하면 됨!
✔ 고립된 노드도 체크해야 하므로 arr[i].isEmpty() 같은 조건 쓰지 말 것!