[백준] 연결 요소의 개수 (BufferedReader, DFS, 11724번, Java)

 

문제설명

입력 & 출력

나의 풀이

---

이번 문제는 방향 없는 그래프가 주어졌을 때, 연결 요소 (Connected Component)의 개수를 구하는 문제입니다.

 

 

먼저 계속해서 호출되는 변수들은 가독성이 좋도록 전역변수로 선언해 줍니다. 그리고 방문 여부를 체크할 visited배열과, 그래프를 저장할 graph배열을 선언해줍니다.

 

 

DFS함수에서는 먼저 인자로 받은 현재위치를 방문 처리해 주고, 현재 노드 node에서 연결된 다음 노드(next) 들을 찾아서, 아직 방문하지 않은 노드들에 대해 DFS함수를 재귀적으로 호출합니다.

 

 

main문에서는 빠른 입력을 위해서 BufferedReader클래스를 사용하여 입력을 받아주고, StringTokenizer를 사용하여 입력받은 간선의 양 끝점 u와 v를 공백을 기준으로 분리하여 각각 저장해 줍니다.

 

입력받은 정점의 개수만큼 배열을 초기화해 주는 데 정점은 1부터 시작하니깐 N+1의 크기만큼 초기화를 해줍니다.

 

입력받은 정점의 정보들을 1로 표시하여 graph에 저장을 해줍니다. 

 

 

그리고 49번째 줄에서 아직 방문하지 않은 정점을 순회합니다. 1을 시작으로 dfs함수에서 연결되어 있는 모든 정점을 순회하고 나오면 count를 증가시켜 연결된 정점의 개수를 구해줍니다.

 

 

참고❗️

[JAVA] 입출력, BufferedReader, StringTokenizer, StringBuilder 알아보기