[백준 / #2667 / C++] 단지번호붙이기

 이 문제는 저번에 다룬 미로 탐색 문제와 상당히 유사하다고 생각한다.

 

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

2667번: 단지번호붙이기

 

 

이 링크는 저번 문제의 링크이다. 문제풀이에서 상당히 겹치는 부분이 많으니 아래 링크를 참고하길 바란다.

 

https://seoul-doggy.tistory.com/4

[백준 / #2178 / C++] 미로 탐색

 

이번 문제는 보자마자 떠올랐다. 너비우선탐색(BFS) 문제이구나.

 

사실 저번 문제에서 아파트의 개수를 세어주는 거만 추가하면 되는 아주 간단한 문제이다.

 

그나저나 이 문제 출처가 초등부,,역시 세상은 넓고 천재는 많다,,,

 

 

우선 코드부터 보자.

 

 

저번 문제에서 크게 벗어나지 않는 문제이다.

 

사실 코드는 거의 똑같고 큐에서 노드를 하나씩 뺄 때마다 개수를 세어주는 거만 제외하면 같다.

 

 

이렇게 개수를 세어주고 한 아파트 단지의 아파트 개수 세기가 완료되면 너비우선탐색을 멈추게 된다. (큐에 더이상 들어

 

 

가있는 노드가 없기 때문) 그러면 아파트의 개수를 return 해주고 이를 ans 벡터에 저장한다. 그렇게 map을 하나씩 돌며

 

 

'1'을 탐색한다. '1' 하나만 찾아도 한 아파트 단지의 탐색이 끝나면 이 단지는 모두 '0'이 되므로 중복이 될 걱정은 안해도 되

 

 

며 하나만 찾아도 그 아파트 단지는 모두 탐색이 되기 때문에 '1' 하나만 찾아도 된다.

 

 

 

 

 map에서 '1'을 찾는 더욱 빠른 알고리즘이 있을 수도 있는데 나는 찾지 못했다. 그리고 문제에서 주어진 쟈료의 최대 크기

 

가 작았기 때문에 (25 X 25) 이중 for문으로도 충분히 커버가 가능할 것이라고 생각했다.

 

 

 

 저번 문제와 너무 비슷한 문제였기 때문에 시간도 얼마 걸리지 않았다. 이상 더 궁금한 점이 있다면 저번 문제의 링크를 참

 

고하면 되겠다.