[백준][C] 2667-단지번호붙이기/인접리스트/그래프/깊이우선탐색/넓이우선탐색

2667 : 단지번호붙이기

2021-08-04

https://www.acmicpc.net/problem/2667

2667번: 단지번호붙이기

<그림 1>과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여

www.acmicpc.net

🏡 시도

처음엔 출력해야할 것이 뭔지 먼저 따져봤다.
- 단지 수와 각 단지에 속하는 집의 수를 오름차순으로 정렬하여 출력해야했다.
  - 단지 수 카운팅을 위한 house_cnt 변수를 선언했고, 각 단지에 속하는 집의 수를 카운팅하기위해 house_cnt 를 index로 사용하여 cnt[house_cnt] 배열에 카운팅했다.
이 문제는 DFS또는 BFS를 사용하는 문제라고 했는데, 어떻게 사용해야할지 감이 안왔지만 차근차근 생각해봤다.
- 1) 집이 없는 자리에는 미리 visited 해놓기
- 2) 맵을 처음부터 방문하다가 visited == 0인 집이 있다면, house_cnt를 증가시키고 그 집부터 DFS(깊이 우선 탐색을 시작한다!)
  - DFS 함수에서는 상 하 좌 우를 검사해보며 인접 집이 있다면 cnt[house_cnt]를 증가시키고 visited 한 다음, 그 위치로 다시 DFS함수를 수행한다.
    - 인접 집이 아무데도 없다면 함수 빠져나오기!
- 3) DFS함수 들어간 그 다음 집 부터 다시 map을 탐색하며 반복수행한다.
정렬은 Bubble Sort를 사용했다. 내 기억에 가장 구현하기 간단한 알고리즘이라 사용해보았다.

🛫코드 구현 [C99]

🧹REVIEW

티스토리툴바