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

구름톤 챌린지 12일차입니다. 챌린지를 통해 문제 풀이 실력을 향상시킬 수 있으며, 블로그에 학습 일기도 작성하면 추가 보상도 주어지니 관심 있으시면 참여해보시는 것을 추천드립니다.

https://level.goorm.io/l/challenge/goormthon-challenge

구름LEVEL

 

문제

입력 / 출력

풀이 과정

집에 전력을 공급하기 위해선 그 집에 발전기를 설치하거나, 상하좌우로 인접한 집 중 하나가 전력을 공급받고 있으면 된다. -> 모여있는 집 그룹의 개수를 세면 된다. 집 그룹 안에 있는 한 집에 발전기를 설치하면 그 그룹의 모든 집에 전기가 공급되기 때문이다.

BFS를 사용해 집 그룹의 개수를 파악했다.

import sys
from collections import deque
input = sys.stdin.readline

n = int(input().rstrip())
maps = [list(map(int, input().rstrip().split())) for _ in range(n)]
visited = [[0 for _ in range(n)] for _ in range(n)]
row = [-1, 1, 0, 0]
col = [0, 0, -1, 1]

result = 0
for i in range(n):
    for j in range(n):
		if visited[i][j] == 0 and maps[i][j] == 1:
			result += 1
			queue = deque()
			queue.append((i, j))
			
			visited[i][j] = 1
			
			while queue:
				y, x = queue.popleft()
				
				for d in range(4):
					ny = y + row[d]
					nx = x + col[d]
					
					if 0 <= ny < n and 0 <= nx < n and maps[ny][nx] == 1 and visited[ny][nx] == 0:
						visited[ny][nx] = 1
						queue.append((ny, nx))
						
print(result)