[Algorithm🧬] 백준 4963 : 섬의 개수

문제

DFS

맞게 짰는데..? Recursion Error 가 나서 BFS 로 다시 풀었다.

import sys

def DFS(i, j):
    # global cnt

    if not 0 <= i < h:
        return False
    if not 0 <= j < w:
        return False

    if town[i][j] == 0:
        return False

    # cnt += 1
    town[i][j] = 0

    for x, y in adj:
        DFS(x + i, y + j)
    return True

# N = int(sys.stdin.readline())

adj = [(-1, 0), (1, 0), (0, -1), (0, 1), (1, 1), (1, -1), (-1, -1),  (-1, 1)]

w = 1
h = 1
while True:
    w, h = map(int, sys.stdin.readline().split())
    if w == 0 or h == 0:
        break
    town = [[int(c) for c in sys.stdin.readline().split()] for _ in range(h)]

    sol = 0

    for i in range(h):
        for j in range(w):
            if town[i][j] == 1:
                DFS(i, j)
                sol += 1

    print(sol)

import sys

def DFS(i, j):
    # global cnt

    if not 0 <= i < N:
        return False
    if not 0 <= j < N:
        return False

    if town[i][j] == 0:
        return False

    # cnt += 1
    town[i][j] = 0

    for x, y in adj:
        DFS(x + i, y + j)
    return True

N = int(sys.stdin.readline())
town = [[int(c) for c in sys.stdin.readline().strip()] for _ in range(N)]
adj = [(-1, 0), (1, 0), (0, -1), (0, 1), (1, 1), (1, -1), (-1, -1),  (-1, 1)]

# cnt = 0
sol = 0

for i in range(N):
    for j in range(N):
        if town[i][j] == 1:
            DFS(i, j)
            sol += 1

print(sol)

BFS

import sys
from collections import deque

def BFS(i, j):
    q = deque()
    q.append((i, j))
    town[i][j] = 0

    while q:
        x, y = q.popleft()

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

            if not 0 <= nx < h:
                continue
            if not 0 <= ny < w:
                continue

            if town[nx][ny] == 1:
                q.append((nx, ny))
                town[nx][ny] = 0


adj = [(-1, 0), (1, 0), (0, -1), (0, 1), (1, 1), (1, -1), (-1, -1),  (-1, 1)]

w = 1
h = 1
while True:
    w, h = map(int, sys.stdin.readline().split())
    if w == 0 or h == 0:
        break
    town = [[int(c) for c in sys.stdin.readline().split()] for _ in range(h)]

    sol = 0


    for i in range(h):
        for j in range(w):
            if town[i][j] == 1:
                BFS(i, j)
                sol += 1

    print(sol)