[Goorm/Python] 발전기 || 구름톤 챌린지 (DFS, BFS)

구름톤 챌린지 발전기 파이썬

구름LEVEL

❍ 문제

구름 심시티를 하고 있는 플레이어는 한 변의 길이가 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 1000$
• $M_{r, c}$는 0 또는 1이다.
• 주어지는 모든 수는 정수이다.

❍ 출력

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

 

❏ 문제 풀이

마을에서 집이 모여있는 덩어리의 개수를 세어주면 되는 것인데 BFS를 통해 문제를 해결할 수 있다.

1. 마을을 탐색하며 집(1)인 경우를 찾는다. 이를 방문 처리를 하고 큐에 삽입한다.
2. 큐에서 노드를 꺼내어 상하좌우에 방문하지 않은 인접한 집(1)이 있는지 확인하고, 모두 큐에 삽입하고 방문 처리를 해준다.

 

<DFS와 BFS>

[Algorithm] DFS와 BFS || Depth-First & Breadth-First Search

 

❍ CODE_BFS

import sys
from collections import deque

input = sys.stdin.readline

n = int(input())
village = [list(map(int, input().split())) for _ in range(n)]

# 상하좌우
direction = [[-1, 0], [1, 0], [0, -1], [0, 1]]

queue = deque()
visited = [[False] * (n) for _ in range(n)]

result = 0
for a in range(n):
    for b in range(n):
        # 집이 있다면
        if village[a][b] == 1 and not visited[a][b]:
            visited[a][b] = True
            result += 1
            queue.append((a, b))
            while queue:
                x, y = queue.popleft()
                # 상하좌우 체크
                for dx, dy in direction:
                    nx = x + dx
                    ny = y + dy
                    # 마을을 벗어난다면, 넘어간다
                    if nx > 0 and nx < n and ny >= 0 and ny < n:
                        # 상하좌우에 집이 있고, 방문한 적이 없다면
                        if village[nx][ny] == 1 and not visited[nx][ny]:
                            visited[nx][ny] = True
                            queue.append((nx, ny))

print(result)

---

물론 DFS로도 풀이가 가능하다.

이전에 비슷한 문제를 풀이한 적이 있어서 그 때의 코드를 참고하여 해결하고자 하였지만, 재귀로는 이 문제가 풀리지 않는다. 따라서, 비재귀 DFS 코드를 참고하여 풀이할 수 있었다.

1. 마을을 탐색하여 집(1)인 경우를 스택에 삽입하고 방문 처리를 한다.
2. 스택의 최상단에 있는 집과 상하좌우로 방문하지 않은 인접한 집이 있다면 모두 스택에 넣고 방문 처리를 한다.
3. 방문하지 않은 인접한 집이 없다면, 스택에서 해당 노드를 꺼낸다.

❍ CODE_DFS

import sys

input = sys.stdin.readline

def dfs(x, y):
    stack = [(x, y)]
    visited[x][y] = True
    while stack:
        x, y = stack.pop()

        for dx, dy in direction:
            nx = x + dx
            ny = y + dy

            # 마을을 벗어난 경우 + 집이 아닌 경우 + 이미 방문한 경우
            if (
                nx in (-1, n)
                or ny in (-1, n)
                or village[nx][ny] == 0
                or visited[nx][ny]
            ):
                continue

            visited[nx][ny] = True
            stack.append((nx, ny))

n = int(input())
village = [list(map(int, input().split())) for _ in range(n)]

# 상하좌우
direction = [[-1, 0], [1, 0], [0, -1], [0, 1]]

visited = [[False] * (n) for _ in range(n)]

result = 0
for i in range(n):
    for j in range(n):
        # 방문하지 않은 집이 있다면 탐색 시작
        if village[i][j] and not visited[i][j]:
            result += 1
            dfs(i, j)
print(result)

---

❏ 삽질 기록

❍ Issue #1

import sys
from collections import deque

input = sys.stdin.readline

n = int(input())
village = [list(map(int, input().split())) for _ in range(n)]

# 상하좌우
direction = [[-1, 0], [1, 0], [0, -1], [0, 1]]

queue = deque()
visited = [[False] * (n) for _ in range(n)]

result = 0
for a in range(n):
    for b in range(n):
        # 집이 있다면
        if village[a][b] == 1 and not visited[a][b]:
            visited[a][b] = True
            result += 1
            queue.append((a, b))
            while queue:
                x, y = queue.popleft()
                # 상하좌우 체크
                for dx, dy in direction:
                    nx = x + dx
                    ny = y + dy

                    # 마을을 벗어난다면, 넘어간다
                    if nx < 0 or nx >= n or ny < 0 or ny >= n:
                        continue

                    # 상하좌우에 집이 있고, 방문한 적이 없다면
                    if village[nx][ny] == 1 and not visited[nx][ny]:
                        visited[nx][ny] = True
                        queue.append((nx, ny))

print(result)

제출했는데, 딱 하나의 케이스에서 시간 초과라는 결과가 발생했다.

는 다시 제출했더니 시간 초과라는 결과 없이 통과가 되었다. 😳😳

그래도 위에서 제출해준 것처럼 조건문을 한번에 해결해주는 것이 더 깔끔해보이고 시간도 더 적게 걸리는 것 같았다..!

 

❍ Issue #2

import sys

input = sys.stdin.readline
sys.setrecursionlimit(10**5)

def dfs(x, y):
    # 마을을 벗어나거나 이미 방문된 곳이라면,
    if x < 0 or x >= n or y < 0 or y >= n:
        return False
    if visited[x][y]:
        return False

    # 방문하지 않은 집이라면,
    if village[x][y] == 1 and not visited[x][y]:
        visited[x][y] = True
        for a, b in direction:
            dfs(x + a, y + b)
        return True
    return False

n = int(input())
village = [list(map(int, input().split())) for _ in range(n)]

# 상하좌우
direction = [[-1, 0], [1, 0], [0, -1], [0, 1]]

visited = [[False] * (n) for _ in range(n)]

result = 0
for i in range(n):
    for j in range(n):
        if village[i][j] == 1 and dfs(i, j):
            result += 1
print(result)

이 코드는 BFS에서 풀이하고 난 후에 DFS로 풀이해본 코드이다. 이전에 책에서 봤던 대로 풀이를 했는데, 런타임 에러가 다수 발생하게 되었다.

sys.setrecursionlimit(10**5) 를 추가해주어 몇 개의 런타임 에러를 해결할 수 있었지만, 그래도 몇 개의 런타임 에러는 여전했다.

결국 풀이를 하지 못했는데, 다음 날 공개된 해설지에서 비재귀 DFS 방식을 참고하여 해결하였다.