[구름톤 챌린지 #12] 발전기

문제12. 발전기

구름LEVEL

---

---

문제 해결 방법

이차원 리스트의 각 칸들을 전부 돌면서, 1이라면(전력공급이 아직 안됐다면) 발전기를 설치하는 문제이다. 중요한 것은 전력이 공급된 곳의 상하좌우에 있는 집도 전력이 공급된다는 것이다. 즉, 발전기를 하나 설치할 때, 연쇄적으로 영향받는 집이 있는지를 체크해줘야한다는 것이다.

 

가장 먼저 생각할 수 있는 것은 재귀함수이다. 전력이 공급된 집의 상하좌우 집들에도 전력 공급이 되고, 또 전력을 공급받은 집의 상하좌우 집들에 전력이 공급된다. 이러한 구조는 재귀로 간단하게 구현할 수 있다. 아래 코드와 같이 상하좌우 집들 중에 아직 전력이 공급되지 않은 집에 한해서 전력을 공급하되 그 상하좌우 집에도 또 다시 전력을 공급할 수 있도록 한다. 이것이 바로 DFS(깊이 우선 탐색)이다. 다만 이렇게 재귀로 만들어진 함수는 많은 경우 recursion error가 발생한다는 점이 문제가 된다.

#runtime error
import sys

sys.setrecursionlimit(50000)

n = int(sys.stdin.readline())

# 인덱스가 넘치는 것을 막기 위해 의미없는 데이터 한줄 늘려줌
arr = [(list(map(int, sys.stdin.readline().split())) + [0]) for i in range(n)]
arr.append([0 for i in range(n + 1)])

dr = [1, -1, 0, 0]
dc = [0, 0, -1, 1]


def power_plant(r, c):
    global arr, dr, dc

    # 0이라면 의미 없음
    if arr[r][c] == 0:
        return

    # 이미 전력이 공급된 곳은 0으로 설정
    arr[r][c] = 0
    # 그 상하좌우에 전력이 공급됨
    for i in range(4):
        power_plant(r + dr[i], c + dc[i])


# 발전기 설치 개수
count = 0
for r in range(n):
    for c in range(n):
        # 0이라면 상관 없음
        if arr[r][c] == 0:
            continue
        # 1이라면 발전소를 설치
        count += 1
        power_plant(r, c)

print(count)

그렇다면 recursion error를 피하려면 어떻게 해야할까? DFS에서 재귀를 사용하지 않고 스택을 사용하도록 코드를 수정할 수도 있지만, 또 다른 방법으로는 BFS(너비 우선 탐색)를 적용하는 방법이 있다. 전력 공급을 체크해야하는 집들을 계속 큐에 집어넣으면서, 큐가 빈 큐가 될 때까지 하나씩 꺼내면서 체크하면 된다. 큐를 사용한다는 점만 떠올릴 수 있다면, 코드로 구현하는 것은 어렵지 않다.

 

위 내용을 코드로 구현하면 아래와 같다.

import sys
from collections import deque

n = int(sys.stdin.readline())
dq = deque()

# 인덱스가 넘치는 것을 막기 위해 의미없는 데이터 한줄 늘려줌
arr = [(list(map(int, sys.stdin.readline().split())) + [0]) for i in range(n)]
arr.append([0 for i in range(n + 1)])

dr = [1, -1, 0, 0]
dc = [0, 0, -1, 1]

count = 0
for r in range(n):
    for c in range(n):
        # 0이라면 상관 없음
        if arr[r][c] == 0:
            continue

        # 1이라면 발전소를 설치 후 상하좌우 탐색을 위해 큐에 집어넣음
        count += 1
        dq.append((r,c))
        while dq:
            #큐에서 하나 꺼내오고
            pop_r, pop_c = dq.popleft()
            #꺼내온게 1이라면 0으로 바꾸고 거기서 다시 상하좌우 뻗어
            if arr[pop_r][pop_c] == 1:
                arr[pop_r][pop_c] = 0
                for i in range(4):
                    dq.append((pop_r+dr[i], pop_c+dc[i]))

print(count)