영역 크기 구하기

나는 탐색 문제를 풀 때 BFS를 선호한다. DFS 개념 자체는 이해하는데 재귀를 문제에 적용하다가 실수하는 경우가 많고 디버깅이 쉽지 않다.

그런데 영역 구할 땐 DFS로 간단하게 구할 수 있어서 익혀두려고 한다.
visited 배열을 사용하지 않아도 알고리즘 구현이 가능하다는 장점이 있다.

영역 구하기(DFS)

...
def dfs(x, y):
    global count

    if x < 0 or y < 0 or x >= n or y >= m:
        return False

    elif graph[x][y] == 0:
        graph[x][y] = 1
        count += 1
        for i in range(4):
            dfs(x+dx[i], y+dy[i])
        return True


answer = []
count = 0
for i in range(n):
    for j in range(m):
        if dfs(i, j):
            answer.append(count)
            count = 0

영역 구하기(BFS)

...
def bfs(x, y):
    queue = deque([[x, y]])
    visited[x][y] = 1
    total = 1
    while queue:
        x, y = queue.popleft()

        for i in range(4):
            mx = x + dx[i]
            my = y + dy[i]

            if mx < 0 or my < 0 or mx >= n or my >= m:
                continue

            if graph[mx][my] == 0 and visited[mx][my] == 0:
                visited[mx][my] = 1
                total += 1
                queue.append([mx, my])

    return total


visited = [[0 for _ in range(m)] for _ in range(n)]
result = []
for i in range(n):
    for j in range(m):
        if graph[i][j] == 0 and visited[i][j] == 0:
            result.append(bfs(i, j))