[구름톤 챌린지] 12일차 - 발전기 [Python]

goorm - 구름톤챌린지 12일차

goorm - 구름톤챌린지 12일차

---

풀이

집에 전력을 공급하기 위해서는 그 집에 발전기를 설치하거나, 해당 집 주변에 전력이 공급되고 있는 집이 있어야 한다.

즉, 상하좌우로 붙어있는 집의 그룹이 몇 개인지 구하는 문제이다.

그룹의 갯수만큼 발전기가 필요하기 때문이다.

bfs로 풀이했다.

 

최적화 테크는 여러 방식이다.

마을 정보를 입력받을 때 집의 위치를 저장해도 되고 마을 전부를 탐색해도 된다.

하지만, 입력 조건에서는 집이 0개일수도, 최대 N^2일 수도 있기 때문에 저장하는 방식보단 빠르게 탐색하는 방식을 선택했다.

bfs로 이어진 집을 전부 탐색한 다음 그룹의 갯수를 세주어 출력하는 방식으로 풀이했다.

집 이고(graph[nx][ny] == 1), 방문하지 않은 집(not visited[nx][ny])을 대상으로 queue에 넣어줬다.

꼭 방문 표시를 해주어야 2중 loop를 돌며 bfs를 진행할 때, 이미 탐색한 집을 중복으로 탐색하지 않고 빠르게 넘어갈 수 있다.

---

출처

구름LEVEL