[CT] 백준 4936 섬의 개수(BFS & DFS)

📎 백준 4836 섬의 개수

📝 문제

2차원 배열이 주어진다. 1은 섬이 있는 곳, 0은 아닌 곳이다. 섬이 있는 곳을 찾아 섬의 개수를 출력하면 된다. 섬은 1이 연결되오 있는 상하좌우, 대각선 모두 허용한다.

BFS, DFS 개념을 잡기에 좋은 문제라 생각한다. BFS, DFS 두가지 풀이로 풀어보았다.

1️⃣ BFS 풀이

from collections import deque
import sys

# 상하좌우 탐색을 위한 전역변수 설정
dx = [-1, -1, 0, 1, 1, 1, 0, -1]
dy = [0, 1, 1, 1, 0, -1, -1, -1]


def house(x, y):
    queue = deque()
    queue.append((x, y))

    while queue:
        x, y = queue.popleft()
        for i in range(8):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < height and 0 <= ny < width and land[nx][ny] == 1:
                land[nx][ny] = 0
                queue.append((nx, ny))


while True:
    width, height = map(int, sys.stdin.readline().split())
    land = [list(map(int, sys.stdin.readline().split())) for _ in range(height)]
    count = 0

    if width == 0 and height == 0:
        break

    for i in range(height):
        for j in range(width):
            if land[i][j] == 1:
                house(i, j)
                count += 1
    print(count)

deque 을 사용하여 섬(1)을 발견할 시 함수가 호출되고 큐에 삽입한다.

그리고 난 후, 큐에 아무것도 없을 때까지 이 행동을 반복한다.

2️⃣ DFS 풀이

import sys
sys.setrecursionlimit(10 ** 6) 

dx = [-1, -1, 0, 1, 1, 1, 0, -1]
dy = [0, 1, 1, 1, 0, -1, -1, -1]


def house(x, y):
    visited[x][y] = 1

    if land[x][y] == 1:
        for i in range(8):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < height and 0 <= ny < width and land[nx][ny] == 1 and not visited[nx][ny]:
                house(nx, ny)


while True:
    width, height = map(int, sys.stdin.readline().split())
    land = [list(map(int, sys.stdin.readline().split())) for _ in range(height)]
    visited = [[0] * width for _ in range(height)]
    count = 0

    if width == 0 and height == 0:
        break

    for i in range(height):
        for j in range(width):
            if land[i][j] == 1 and not visited[i][j]:
                house(i, j)
                count += 1
    print(count)

BFS 와 다른점은 스택을 이용한다는 점이다. 또한 방문여부를 확인하기 위해 0 으로 초기화 된 방분배열을 만들었다.

섬(1) 을 만나거나 아직 방문하지 않았으면 함수를 호출하여 재귀를 호출한다.

🤔 sys.setrecursionlimit(10 ** 6)

• 재귀 깊이 제한을 변경한다.
• 파이썬의 재귀 최대 깊이의 기본 설정이 1,000회