연결된 컴포넌트
정의
- 연결된 하위 그래프를 말하며 연결된 하나의 덩어리라 보면 된다
- 이 덩어리는 연결된 컴포넌트에 속한 "모든 정점을 연결하는 경로가 있다"는 특징을 갖는다
풀르드필(floodfill)
- 위의 그림에서 연결된 컴포넌트의 수는 3개이고 각각의 컴포넌트는 2개, 3개, 2개의 정점을 갖는다
- 즉 연결되어 있는지 아닌지를 토대로 연결된 컴포넌트로 나눠 각각의 컴포넌트에 번호를 붙여 색칠하는 알고리즘이 풀르드필 알고리즘이다
'코딩 태스트 > 개념' 카테고리의 다른 글
| 너비우선탐색(BFS, Breadth First Search) (0) | 2025.01.10 |
|---|---|
| 깊이우선탐색(DFS, Depth First Search) (1) | 2025.01.10 |
| 맵과 방향 벡터(Direction Vector) (0) | 2025.01.10 |
| 인접 행렬과 인접 리스트 차이 (0) | 2025.01.10 |
| 인접리스트(Adiacency List) (0) | 2025.01.10 |