문제 링크
2667번: 단지번호붙이기
<그림 1>과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여
www.acmicpc.net
문제 설명
<그림 1> 과 같은 2차원 배열이 주어졌을 때 1은 집이 있는 곳 0은 집이 없는 곳이다. 연결되어 있는 집들은 하나의 단지로 보고 총 단지 수와 단지에 속하는 집의 수를 오름차순으로 출력해야 한다.
문제 풀이
완전 탐색을 통해 값이 1이고 방문하지 않았다면 해당 위치부터 BFS(또는 DFS)를 돌려 단지를 찾아내고 단지에 속하는 집의 수를 벡터에 저장한다.
완전 탐색이 종료되면 벡터를 오름차순으로 정렬하여 출력해준다.
코드
