구름톤 챌린지 3주 차 학습 일기(Day 02)

문제

구름 심시티를 하고 있는 플레이어는 한 변의 길이가 N인 정사각형 모양의 마을 M을 만들고 있다. r번째 행, c번째 열에 해당하는 칸에는 숫자 M(r,c)가 적혀 있다. M(r,c)는 0또는 1중 하나이며, 각 숫자가 의미하는 바는 아래와 같다.

- 0이면 아무것도 없는 칸이다.
- 1이면 집이 있는 칸이다.
마을에 있는 집에 전력을 공급하기 위해선 그 집에 발전기를 설치하거나, 상하좌우로 인접한 집 중 하나가 전력을 공급받고 있으면 된다. 플레이어가 모든 집에 전력을 공급하기 위해서 설치해야 할 발전기의 최소 개수를 구해보자.

 

 

 

코드

from sys import stdin as s
from collections import deque

def bfs(si,sj):
	global count
	v[si][sj] = 1
	
	while q:
		ci,cj = q.popleft()
		
		dx = [0,1,0,-1]
		dy = [1,0,-1,0]
		
		for i in range(4):
			nx = dx[i] + ci
			ny = dy[i] + cj
			
			if 0<=nx<N and 0<=ny<N:
				if house[nx][ny] == 1 and not v[nx][ny]:
					q.append((nx,ny))
					v[nx][ny]=1
	count+=1
if __name__=="__main__":
	N = int(s.readline())
	house = [list(map(int,s.readline().split())) for _ in range(N)]
	count = 0
	v=[[0]*N for _ in range(N)]
	q=deque()
	for i in range(N):
		for j in range(N):
			if house[i][j] == 1:
				if not v[i][j]:
					q.append((i,j))
					bfs(i,j)
	print(count)

 

 

 

느낀점

이 문제는 상,하,좌,우로 집이 인접한 경우 한번에 처리되는 식으로 처리해서 전체 반복이 끝나면 count를 늘리는 방법으로 풀이했습니다.

일반 bfs문제를 살짝 활용해서 집의 위치를 찾고 q에넣은다음에 그 집에서 한번에 이어질 수 있는 모든 집을 탐색을 하고 count를 늘려줍니다. 

방문 체크와 q에 넣는 것만 신경쓰면 크게 어렵지 않게 풀 수 있을 것 같습니다.