연결된 컴포넌트(Connected Component)

연결된 컴포넌트란

이거다

오 뭔가 그거같다.

꽁낑낑꽁꽁깡꽁낑꽁꽁

아 피곤해서 이해좀 해주세요:)

 

그래서 연결된 컴포넌트는 연결된 하나의 덩어리라고 보시면 됩니다.

이렇게 연결된 컴포넌트에 속한 "모든 정점을 연결하는 경로가 있다!" 라는 특징을 가져요.

1과 2는 연결되어 있고 모든 정점은 1과 2밖에 없죠

그러면 연결된 컴포넌트입니다.

 

그래서

이는 연결된 컴포넌트의 개수는 3개이며 각 정점은 2개 3개 2개입니다.

 

그러면 이것을 각각 번호를 매겨봅시다.

이런식으로 번호를 부여한 알고리즘을 flood fill이라고합니다.

 

우리는 저번 포스팅에서 맵을 배웠었죠?

위 사진과 같은 맵이 있을 때 1은 갈 수 있는 곳 0은 갈수 없는 곳이라고 했을 때 연결된 컴포넌트의 개수는 몇개일까요?

이렇게 3개의 연결된 컴포넌트를 발견했습니다.

그렇다면 이런식으로 번호를 붙히면 이렇게 되겠습니다.

 

끄으으으으으으트ㅡ틑