[BOJ] 백준 11724 연결 요소의 개수 (JAVA)

그래프 탐색 기본!

---

📑 문제

 

백준 11724 연결 요소의 개수

---

본문에서 "방향 없는 그래프가 주어졌을 때" 라는 말은 곧 양방향이다!
즉 A -> B , B -> A 가 성립해야 한다.

 

"연결 요소"에 대해 설명하기 위해 테스트 케이스를 두 가지를 가져와 봤다.

1. 본문 예제 입력 1

예제 입력 1번 그래프

 

위 사진은 본문에서 입력된 정점과 간선들의 그래프이다.

왼쪽 집합 (1,2,5) 와 오른쪽 집합 (3,4,6)은 연결할 수 있는 간선이 없다 즉 "연결 요소의 개수는" 2 가 되는 것이다!

 

2. TestCase : 4 0

이 경우는 노드는 4개이고 간선은 0이다 그렇다면 연결 요소의 개수는 몇일까?

TestCase : 4 0

답은 4 이다. 간선이 없는 노드는 하나의 연결요소이다. 이점만 생각하고 구현한다면 쉽게 풀 수 있을 것이다.

 

---

🌱 코드 및 풀이

ArrayList를 이용하여 인접리스트를 만들고 양방향임을 고려하여 인접리스트에 저장해 준다!

 

dfs() : dfs를 이용하여 최대로 연결 가능한 노드까지 탐색한다. ex) A -> B -> C

최대로 연결 가능한 노드까지 탐색을 끝낸다면, 그다음 아직 탐색하지 않은 노드를 기점으로 다시 dfs 함수를 실행한다.

 

이렇게 된다면 main함수에서 실행된 dfs() 수가 곧 연결요소의 개수가 된다!

 

---

🌱 느낀 점

Java 평균만큼 나온 것 같다

 

더 깊게 생각해 보면 실행속도를 줄일 수 있는 방법이 있을 것 같다 ㅎㅎ 나중에 다시 고민해 봐야겠다

최근 배웠던 다익스트라 알고리즘에서 동적배열을 활용한 인접리스트 구현방법을 배웠는데

이 문제를 해결하는데 큰 도움이 된 것 같다! 

그래프 탐색 쪽 알고리즘은 배울수록 재밌다 ㅎㅎ