[구름톤 챌린지] 3주차 12일차 발전기

문제

---

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

 

 

• $0$이면 아무것도 없는 칸이다.
• $1$이면 집이 있는 칸이다.

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

입력

---

첫째 줄에 마을의 크기 $N$이 주어진다.
다음 $N$개의 줄에는 마을의 상태를 나타내는 $N$개의 숫자가 공백을 두고 주어진다. $r$번째 줄에서 $c$번째로 주어지는 값이 $M_{r, c}$에 해당한다.

 

 

• $1 \leq N \leq 1 \ 000$
• $M_{r, c}$는 $0$또는 $1$이다.
• 주어지는 모든 수는 정수이다.

출력

---

플레이어가 모든 집에 전력을 공급하기 위해서 설치해야 할 발전기의 최소 개수를 출력한다.

 

---

문제 접근 방식

---

그래프 탐색 문제로, BFS를 활용하거나 DFS를 활용하면 해결할 수 있다.

 

두가지 중 하나의 방법을 활용하여 그래프의 연결 요소를 세면 되는 문제이다.

 

유니온 파인드로도 해결할 수 있을 것 같긴한데, 제한이 크다.

 

나의 경우는 BFS로 해결하였다. DFS로 해결하려고 한다면, 파이썬은 재귀 메모리를 많이 차지하기 때문에 스택으로 구현해야 할 것이다.

 

---

정답 코드

---

# 발전기
import sys
input = sys.stdin.readline
from collections import deque

N = int(input())
M = [list(map(int, input().rstrip().split())) for _ in range(N)]
cnt = 0
dr = [-1, 1, 0, 0]
dc = [0, 0, -1, 1]
def BFS(r, c):
    queue = deque()
    queue.append((r, c))
    M[r][c] = 0
    while queue:
        nr, nc = queue.popleft()
        for i in range(4):
            nnr, nnc = nr+dr[i], nc+dc[i]
            if 0 <= nnr < N and 0 <= nnc < N and M[nnr][nnc]:
                M[nnr][nnc] = 0
                queue.append((nnr, nnc))
    return 1

total = 0
for r in range(N):
    for c in range(N):
        if M[r][c]:
            total += BFS(r, c)
print(total)

 

---

특별히 배운 점

---

오랜만에 그래프 탐색 문제를 풀어서 복습도 되고 좋은 경험이었다.