2667 - 단지번호 붙이기

문제 요약

1. 입력으로는 동네 지도가 들어온다. 0은 집이 없는 거리, 공원등이고 1은 아파트이다.
2. 인접한 아파트들을 묶어서 단지라고 부른다. (인접한 아파트란 상하좌우에 있는 아파트들) 아래 지도에는 3개의 아파트 단지가 있다.
   
3. 만약 지도가 입력으로 주어졌을 때, 지도에는 몇개의 아파트 단지가 있을까?

접근법

이러한 문제역시 BFS 문제중 굉장히 빈번하게 출제되는 문제다. 백준에도 비슷한 문제가 많이 올라와 있고, 심지어는 카카오에서 진행한 카카오 코딩 페스티벌 문제에도 출제된적이 있다. 물론 많이 나오는 문제인 만큼 정답률도 약 60%로 높았다. 처음 보면 어렵다고 느껴질 수 있는 문제지만 한번만 풀어보면 어렵지 않다고 생각하게 될것이다.

지도의 좌측 상단에서 부터 우측 하단까지 지도를 확인하며 아파트 단지이면 BFS를 시작한다. 만약 현재 위치에 아파트가 있다면 (현재 위치가 1이라면) 현재위치와 붙어 있는 아파트 단지를 전부 탐색한다. 이 때 현재 위치의 아파트를 하나의 단지로 묶은 적이 없어야 한다. 현재 위치의 아파트에서 상하좌우 이동하며 인접한 아파트를 찾고 이렇게 찾은 아파트들은 하나의 단지로 묶었다는 의미에서 history Buffer에 1로 표시한다. 이렇게 1개의 아파트를 묶을 때마다 카운터를 1개씩 증가시켜 나가고, 우측 하단까지 전부 지도를 확인했으면 누적된 카운터를 출력하므로써 문제를 해결할 수 있다.

기존의 BFS 문제와 차이점이라면 기존 문제들은 1번의 BFS만 진행했지만 이번 문제는 해결하기 위해서 1번 이상의 BFS를 사용해야 한다. 또한 여러번에 거쳐 진행되는 BFS들이 history Buffer를 공유한다는 것이 차이점이라 할수 있다. 아마 이번 문제를 풀었으면 카카오 코딩 페스티벌에 나온 컬러링북 문제도 쉽게 풀수 있지 않을까 생각한다.

Source Code

소스코드 보러가기

• 아직 주석이 달려있지 않습니다.
• pseudocode 보다는 python 코드를 올릴 예정입니다.
• Code Review는 언제나 환영합니다 (코드를 더 깔끔하게, 효율적으로 만드는걸 도와주세요!)