[구름] 발전기 (python)

문제

https://level.goorm.io/exam/195694/%EB%B0%9C%EC%A0%84%EA%B8%B0/quiz/1

구름LEVEL

 

 

코드

from collections import deque

N = int(input())
my_map = [list(map(int, input().split())) for _ in range(N)]
answer = 0
dx = [1, -1, 0, 0]
dy = [0, 0, -1, 1]
visited = [[False] * N for _ in range(N)]
queue = deque()

for i in range(N):
	for j in range(N):
		if my_map[i][j] == 1 and not visited[i][j]:
			queue.append((i, j))
			visited[i][j] = True
			
			while queue:
				x, y = queue.popleft()				
				for k in range(4):
					nx, ny = x+dx[k], y+dy[k]
					if 0<=nx<N and 0<=ny<N and my_map[nx][ny] and not visited[nx][ny]:
						queue.append((nx, ny))
						visited[nx][ny] = True
						
			answer += 1
		
print(answer)

 

상하좌우를 확인하기 위해 dx, dy를 선언해주고

이전에 방문했는지 여부를 저장하기 위해 visited 배열을 선언해주었다.

 

플레이어가 모든 집에 전력을 공급하기 위해서 설치해야 할 발전기의 최소 개수를 구하는 문제이므로 BFS 알고리즘을 적용해 풀었다.

집이 있는 칸(1) 이라면 queue에 넣었고

그 칸을 시작으로, 주변을 훑으면서 인접한 집이 있는 경우에 queue에 추가, visited=True 설정해주었다.

그리고 queue를 다 훑고 끝났을 때 answer += 1 해줌으로써 발전기의 개수를 셋팅해주었다.

마지막에 answer은  발전기의 최소 개수를 반환한다.