문제
구름 심시티를 하고 있는 플레이어는 한 변의 길이가 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에 넣는 것만 신경쓰면 크게 어렵지 않게 풀 수 있을 것 같습니다.
