연결된 노드들 중에 그룹의 개수를 구하기

노드가 N개 존재하는데 그 중에 임의의 노드들끼리 연결되어 있는데

연결된 노드끼리 하나의 그룹이라고 할때 그룹의 총 개수를 구하기

 

1. 방문하지 않은 노드 선정, 그룹 개수 추가

2. 현재 노드를 방문처리

3. 현재 노드에서 갈 수 있는 모든 노드를 Que에 추가

4. Que에서 하나의 노드를 꺼냄

5. Que가 빌때까지 2~4 를 반복

6. Que가 빈 상태에서 아직 방문하지 않은 노드가 있으면 1번부터 다시 시작

 

---

 

2차원 배열로 된 표로 생각하면

1. 방문하지 않은 노드 선정, 그룹 개수 추가

1 (노드 선정)	1	0
1	1	0
0	0	1

2. 현재 노드를 방문처리

0 (방문 처리)	1	0
1	1	0
0	0	1

3. 현재 노드에서 갈 수 있는 모든 노드를 Que에 추가

0	1 (Que 추가)	0
1	1	0
0	0	1

4. Que에서 하나의 노드를 꺼냄

0	0 (Que 꺼냄)	0
1	1	0
0	0	1

5. Que가 빌때까지 2~4 를 반복

0	0	0
1	1 (현재 노드)	0
0	0	1

0	0	0
1	0 (방문처리)	0
0	0	1

0	0	0
1 (Que 추가)	0	0
0	0	1

0	0	0
0 (Que 꺼냄)	0	0
0	0	1

0 (이미 방문한 노드)	0	0
0	0	0
0	0	1

6. Que가 빈 상태에서 아직 방문하지 않은 노드가 있으면 1번부터 다시 시작

0	0	0
0	0	0
0	0	1 (노드 선정)