Binary Tree Level Order Traversal - BFS / Tree / Queue

트리를 레벨별로 출력하라는 문제. 예를 들어, Root 가 1이고, 좌우 Child가 2, 3, 그 다음 세대가 각각 4/5, 6/7인 경우에는 -> [[1],[2,3],[4,5,6,7]] 처럼 출력하는 문제이다.

이건 레이어가 중요한 문제

BFS의 경우에 어떤 경우는 queue에 자식노드를 계속 추가하면서 while로 해서 다 방문하고, 지금 경우는 for 로 딱 현재 queue 길이만큼만 방문하되 자식 노드는 추가는 계속 해 나가기도 한다. 후자의 경우는 레벨별로 방문해야 하거나, 아니면 최단거리 문제를 풀어야 할 때 꼭 지켜줘야 하는 것이다. 아래 코드에 설명을 달아 둔다.

from collections import deque

class Solution:
    def levelOrder(self, root):
        if not root:
            return []
        
        # 여기부터 통상의 bfs(root) 코드의 바디가 되는 부분임
        q = deque([root])  # deque 설정해주고
        res = []

        while q:  # queue가 있는 동안은 계속 돈다
            level = []

            for _ in range(len(q)):  # len(q) 에 대해서만 딱 재서, 그만큼만 방문(처음엔 [1])
                node = q.popleft()
                level.append(node.val)  # 이게 방문(예. `1`)

                if node.left:
                    q.append(node.left)  # 방문하지는 않고 queue에 다음 방문할 곳 추가(`2`)
                if node.right:
                    q.append(node.right) # 마찬가지(`3`). 만약 4방향 방문이면 이런게 2줄 더 있겠지요

            res.append(level)  # while은 layer 단위(예. [1])로 반복하기 위한 것입니다

        return res

이걸 트리 문제라고 생각하면 일반적 원칙에서 이해가 되지 않을 수 있지만, bfs의 Shortest Path 유형이라 생각하면 2방향만 탐색하는 그래프 문제라고 통일해서 접근할 수 있다.

레이어가 안중요한 문제

그렇다면, layer 상관없이 푸는 bfs 문제는 뭐가 있을까. 섬 숫자 세기를 들어본다 (LeetCode #200). 예를 들어 다음 2D matrix가 있을 때, 1은 땅이고 0은 물이면, 1로 연결된 영역 즉 island가 몇 개 인가? 하는 문제다. bfs나 dfs나 방문만 잘 하면 상관없다. 일단 섬으로 보이는 곳("1")에 발을 들이고, 거기서부터 인접한 모든 "1"을 다 방문한다. bfs나 dfs나 인접한 건 다 방문을 할 거니까, bfs 시작점("1"인 셀)에서 island += 1 한다.

이 때는 layer가 중요하지 않다. 그러므로 레이어별 방문할 필요가 없어서 위에 while 하나만 신경쓰면 된다. 그 안에 for가 있지만 그건 혼동할 필요가 없는게, directions 를 4가지 다 방문하려고 쓴 for 이지, 방문할 layer의 길이만큼을 방문하려는 for가 아니다. 위 문제의 코드에서 if node.left랑 if node.right에 상응하는 액션이다. 단지 여기서는 방문할 child node가 4개라서 귀찮으니 for로 바꾼 것 뿐이다.

Input: grid = [
  ["1","1","1","1","0"],
  ["1","1","0","1","0"],
  ["1","1","0","0","0"],
  ["0","0","0","0","0"]
]
Output: 1

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        directions = [[1, 0], [-1, 0], [0, 1], [0, -1]]
        ROWS, COLS = len(grid), len(grid[0])
        islands = 0

        def bfs(r, c):
            q = deque()
            grid[r][c] = "0"  # mark visited so that further traversal cannot visit this
            q.append((r, c))

            while q:
                row, col = q.popleft()     # changing to `pop()` for dfs
                for dr, dc in directions:  # traverse 4 directions
                    nr, nc = dr + row, dc + col
                    if (nr < 0 or nc < 0 or    # OOB
                        nr >= ROWS or nc >= COLS or   # OOB
                        grid[nr][nc] == "0"    # visited
                    ):
                        continue
                    q.append((nr, nc))   # `will` visit, so append child nodes
                    grid[nr][nc] = "0"   # mark visited

        for r in range(ROWS):
            for c in range(COLS):
                if grid[r][c] == "1":    # if not visited
                    bfs(r, c)      # try visiting one random cell
                    islands += 1   # count up as a bfs will visit all territory of island

        return islands
        
# https://neetcode.io/problems/count-number-of-islands/solution

위 두가지 유형을 구분하면 bfs 탐색 문제는 혼동하지 않을 수 있을 것이다.

Connected Components

두 번째 '섬' 문제는 결국 Number of Connected Components in an Undirected Graph랑 같은 문제이다. 다만 다루기 좋게 nested array로 자료가 제시되었을 뿐이다. 만약에 저 자료를 edges의 리스트로 준다면(edges[i] = [ai, bi]), adjacency list로 처리하도록 하는 단계가 추가로 필요할 뿐이다.

class Solution:
    def countComponents(self, n: int, edges: List[List[int]]) -> int:
        adj = [[] for _ in range(n)]
        visit = [False] * n
        for u, v in edges:
            adj[u].append(v)  # list of edges -> adjacency list reformat
            adj[v].append(u)  # ... for both directions as the graph's undirected

        def dfs(node):
            for nei in adj[node]:
                if not visit[nei]:
                    visit[nei] = True  # mark visited
                    dfs(nei)

	# populating primer has the same fractal pattern as the child process, dfs
        res = 0
        for node in range(n):
            if not visit[node]:
                visit[node] = True
                dfs(node)
                res += 1
        return res

# https://neetcode.io/problems/count-connected-components/solution

Union-Find

그런데 이런 섬 개수 문제는 Union-Find로도 풀 수 있다. 각 land 셀("1") 혹은 node을 처음에는 독립된 컴포넌트로 보고, 초기 컴포넌트 수의 추정치를 일단 land의 개수를 갖다가 설정한다. 이후 서로 인접한 land 셀(혹은 node)을 union 하며, 서로 다른 컴포넌트가 실제로 합쳐질 때마다 컴포넌트 수를 1 줄인다. 두 회사를 합병할 때 마다 회사 숫자가 1씩 줄어드는 것과 같다.

일관된 설명을 위해 문제 2를 갖고 설명해 본다. 내가 어떤 회사의 3차 계열사인데, 또 무슨 회사가 나랑 같은 소속인지 보려면 그 최종 모회사를 알아내어(Find) 둘이 같은 모회사로부터 나왔는지를 보면 된다. 근데 트리 깊이를 작게 하는 것이 향후 검색에서도 효율적이니까, 합병시에는 rank라고 불리는 트리의 높이 근사치를 비교하여,

- rank가 다르면 작은 쪽을 큰 쪽 밑에 붙임
- rank가 같을 때만 한쪽을 루트로 삼고
- 그 루트의 rank를 1 증가

한다. 여튼 핵심적인 개념은 합병(Union) 이다. 그리고 이를 위해 모회사를 찾는(FInd) 것이다. 그러므로 이름 그 자체의 두 메소드를 정의하면 된다.

class DSU:  # Disjoint Set Union
    def __init__(self, n):
        # 각 노드의 부모를 저장. 처음에는 자기 자신이 부모(=각 노드가 독립 컴포넌트)
        self.parent = list(range(n))
        # 각 루트가 대표하는 트리의 "높이" (union 시 작은 트리를 큰 트리 밑에 붙이기 위한 정보)
        self.rank = [1] * n

    def find(self, node):
        # node가 속한 컴포넌트의 루트(대표 노드)를 찾는다
        cur = node
        # 루트 조건: parent[x] == x
        while cur != self.parent[cur]:
            # path compression: 현재 노드를 "할아버지"에 바로 연결
            # → 트리 높이를 줄여 이후 find를 빠르게 함
            self.parent[cur] = self.parent[self.parent[cur]]
            # 한 단계 위로 올라가 계속 루트를 찾음
            cur = self.parent[cur]
        # 최종적으로 찾은 루트 반환
        return cur

    def union(self, u, v):
        # 두 노드가 속한 컴포넌트의 루트를 찾음
        pu, pv = self.find(u), self.find(v)

        # 이미 같은 컴포넌트라면 합칠 필요 없음
        if pu == pv:
            return False

        # union by size(rank):
        # 작은 트리를 큰 트리 밑에 붙여 트리 높이 증가를 최소화
        if self.rank[pv] > self.rank[pu]:
            pu, pv = pv, pu

        # pv 트리를 pu 밑으로 붙임 (두 컴포넌트를 하나로 합침)
        self.parent[pv] = pu

        # pu가 대표하는 컴포넌트 크기 업데이트
        self.rank[pu] += self.rank[pv]

        # 실제로 두 컴포넌트가 합쳐졌음을 알림
        return True


class Solution:
    def countComponents(self, n: int, edges: List[List[int]]) -> int:
        # n개의 노드로 DSU 초기화 (처음엔 n개의 독립 컴포넌트)
        dsu = DSU(n)

        # 초기 컴포넌트 개수 = 노드 개수
        res = n

        # 모든 edge를 보며 두 노드를 union 시도
        for u, v in edges:
            # union이 성공했다면 서로 다른 컴포넌트가 하나로 합쳐진 것
            if dsu.union(u, v):
                # 컴포넌트 수 1 감소
                res -= 1

        # 남은 컴포넌트 개수 반환
        return res


# https://neetcode.io/solutions/number-of-connected-components-in-an-undirected-graph