연결 요소와 플러드 필

"이 네트워크에 따로 노는 친구 그룹이 몇 개지? 이 지도에 섬이 몇 개지? 둘은 사실 같은 질문이야. 끊어진 조각이 몇 개냐는 거지. 그리고 안 가본 노드마다 BFS나 DFS를 한 번씩 돌리면 답이 나와."

연결 요소

연결 요소(connected component)는 무방향 그래프에서 서로 닿을 수 있는 노드들의 최대 묶음이야. 모든 노드를 돌면서 아직 안 가본 노드에서 BFS나 DFS를 시작하면, 한 번의 순회가 요소 하나를 덮고 시작한 횟수가 곧 요소 개수가 돼. 전체가 O(V+E)고. 방향 그래프에서는 "연결"이라는 말이 하나가 아니라는 걸 조심해. 방향을 무시하고 보는 약한 연결 요소와, 양쪽으로 다 갈 수 있는 강한 연결 요소를 구분해야 하거든.

플러드 필: 격자에서 같은 아이디어

2차원 격자는 사실 그래프야. 각 셀이 노드고 위아래 양옆의 인접 셀이 그 이웃이지. 그래서 페인트통 도구도, "섬 세기"도, 이미지의 영역 검출도 전부 플러드 필이야. 셀 하나에서 시작해 같은 색으로 이어진 셀 전체를 BFS나 DFS로 훑으면서 칠해 나가는 거지. "섬 개수"는 말 그대로 "땅 셀의 연결 요소 세기"야. 격자 좌표가 노드가 되고 인접이 암묵적인 간선이 될 뿐, 돌고 채우는 패턴은 똑같아. 격자를 그래프로 알아보는 것, 이게 이 트랙 전체에서 가장 효과가 큰 관점 전환이야.

연결 요소는 아직 안 가본 노드마다 BFS나 DFS를 시작해서 세면 돼. 시작한 횟수가 요소 개수고 전체가 O(V+E)야. 격자는 그 자체로 그래프라서(셀이 노드, 인접이 간선) 플러드 필과 섬 세기가 똑같이 돌고 채우는 패턴이고.

사촌: 이분 그래프 확인 (2-색칠)

같은 순회 골격이 또 다른 고전 문제에도 답해. 이 그래프가 이분 그래프(bipartite)인가, 그러니까 모든 간선이 두 그룹 사이를 건너가도록, 한 그룹 안에는 간선이 없도록 노드를 둘로 나눌 수 있는가 하는 문제야. BFS나 DFS를 돌리면서 두 가지 색으로 칠해 보면 돼. 간선을 건널 때마다 색을 바꾸는 거지. 그러다 이미 인접한 두 노드에 같은 색을 줘야 하는 상황이 오면 이분 그래프가 아니야. '내부 충돌 없이 두 팀으로 나눌 수 있나?'를 모델링하는 거라 스케줄링, 매칭, 충돌 검출에 쓰여. BFS와 DFS가 하나의 알고리즘이 아니라 서로 다른 장부를 걸어 쓰는 골격이라는 걸 다시 확인시켜 주는 예이기도 하고.

피파의 고백

"섬 세기"에서 완전히 막혀 있었는데 아빠가 물었어. "각 격자 셀이 그래프 노드면?" 그 순간 문제가 통째로 녹았어. 인접한 네 셀이 이웃인 연결 요소 문제일 뿐이었거든. 나는 격자 좌표를 뒤집어쓴 그래프 문제를 격자 문제로만 노려보고 있었던 거야. 그 뒤로는 격자를 보면 조용히 물어봐. 셀을 노드로 바꾸면 이 어려워 보이는 퍼즐이 내가 이미 아는 BFS가 되는 건 아닐까 하고.

Code

연결 요소와 섬 플러드 필·python

# 연결 요소 세기: 요소당 DFS 시작 한 번.
def count_components(graph):
    visited, count = set(), 0
    def dfs(node):
        visited.add(node)
        for nb in graph[node]:
            if nb not in visited:
                dfs(nb)
    for node in graph:
        if node not in visited:
            count += 1            # 새 시작 = 새 요소
            dfs(node)
    return count

g = {"A":["B"], "B":["A"], "C":["D"], "D":["C"], "E":[]}
print("components:", count_components(g))   # 3  ({A,B}, {C,D}, {E})

# 섬 개수: 격자가 그래프. 각 땅 영역을 플러드-필.
def num_islands(grid):
    if not grid: return 0
    rows, cols, count = len(grid), len(grid[0]), 0
    def flood(r, c):
        if not (0 <= r < rows and 0 <= c < cols) or grid[r][c] != "1":
            return
        grid[r][c] = "0"          # '가라앉혀' 재방문 안 함 (visited 표시)
        flood(r+1, c); flood(r-1, c); flood(r, c+1); flood(r, c-1)
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == "1":
                count += 1        # 새 땅 셀 = 새 섬
                flood(r, c)
    return count

ocean = [["1","1","0","0"], ["1","0","0","1"], ["0","0","1","1"]]
print("islands:", num_islands(ocean))   # 2

Exercise

1이 땅이고 0이 물인 격자가 있어. 땅 셀이 대각선은 빼고 위아래 양옆으로만 이어진다고 할 때, 플러드 필이 어떻게 섬을 세는지와 '방문 집합' 역할을 무엇이 대신하는지 설명해 봐. 그다음, 대각선으로 붙은 것도 인접으로 치면 답이 어떻게 달라지고 코드의 어느 부분을 고쳐야 할까?

Hint

모든 셀을 돌면서 아직 안 가본 땅 셀을 만나면 개수를 하나 올리고 거기서 이어진 영역 전체를 DFS나 BFS로 채워. 셀을 0으로 가라앉히는 게 방문 표시 역할을 하고. 대각선까지 인접으로 치려면 flood의 재귀 호출에 대각선 이웃 네 개를 추가하면 되는데, 그러면 섬이 더 적어지고 대신 하나하나가 더 커져.

연결 요소

플러드 필: 격자에서 같은 아이디어

사촌: 이분 그래프 확인 (2-색칠)

피파의 고백

Code

External links

Exercise

Progress

댓글 0