https://www.acmicpc.net/problem/2667
2667번: 단지번호붙이기
<그림 1>과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집들의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여기서 연결되었다는 것은 어떤 집이 좌우, 혹은 아래위로 다른 집이 있는 경우를 말한다. 대각선상에 집이 있는 경우는 연결된 것이 아니다. <그림 2>는 <그림 1>을 단지별로 번호를 붙인 것이다. 지도를 입력하여 단지수를 출력하고, 각 단지에 속하는 집의 수
www.acmicpc.net
문제 설명
방문 처리가 되지 않은 지점이면서 집인 경우에 bfs를 수행해준다.
한 번 수행할 때마다 단지를 하나씩 찾게 되므로, bfs 함수가 실행될 때 단지의 수를 증가시킨다.
이어서 각 단지마다 집의 개수를 파악해야 한다.
이는 bfs를 수행하면서 큐에 push 되는 횟수를 저장해주면 된다. 당연하게도 집인 경우에만 다음에 이어서 탐색을 하도록 구현했으니까.
주의할 것은, 시작지점 즉 bfs를 시작하는 지점도 집이라는 사실이다. 따라서 단지 내 집의 개수를 저장하는 변수인 homeCnt를 1로 초기화했다.
그리고 초기에는 단지 전체의 수를 저장할 변수도 있었는데, 벡터를 사용하게 되면 벡터의 크기가 곧 단지의 개수가 될 것이기 때문에 이것으로 대신했다.
'알고리즘 문제 풀이 > 백준 온라인 저지' 카테고리의 다른 글
| 백준 15656번: N과 M (7) (C++) (0) | 2019.07.18 |
|---|---|
| 백준 2667번: 단지번호붙이기 (DFS) (C++) (0) | 2019.07.18 |
| 백준 9466번: 텀 프로젝트 (C++) (0) | 2019.07.18 |
| 백준 15655번: N과 M (6) (C++) (0) | 2019.07.17 |
| 백준 15652번: N과 M (5) (C++) (0) | 2019.07.17 |