FAANG 코딩 인터뷰 완전 정복: 트리와 그래프 핵심 패턴

트리와 그래프 문제는 FAANG 인터뷰에서 배열/문자열 다음으로 출제 빈도가 높습니다. 특히 Google, Meta에서 그래프와 트리 탐색 문제를 매우 중요하게 봅니다. 이 글에서는 인터뷰 필수 패턴 5가지를 완전한 Python 코드와 함께 정복합니다.

1. Binary Tree 핵심 패턴

DFS (Depth-First Search)

DFS는 깊이 우선으로 트리를 탐색합니다. 재귀와 반복(스택) 두 가지 방식으로 구현할 수 있습니다.

트리 노드 정의

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

DFS 순회 3가지 (재귀)

# Inorder: 왼쪽 → 현재 → 오른쪽 (BST에서 정렬된 순서)
def inorder(root):
    if not root:
        return []
    return inorder(root.left) + [root.val] + inorder(root.right)

# Preorder: 현재 → 왼쪽 → 오른쪽 (트리 복사, 직렬화)
def preorder(root):
    if not root:
        return []
    return [root.val] + preorder(root.left) + preorder(root.right)

# Postorder: 왼쪽 → 오른쪽 → 현재 (디렉토리 크기 계산)
def postorder(root):
    if not root:
        return []
    return postorder(root.left) + postorder(root.right) + [root.val]

DFS 반복 구현 (스택 사용)

def inorderIterative(root):
    result = []
    stack = []
    current = root

    while current or stack:
        # 가장 왼쪽으로 이동
        while current:
            stack.append(current)
            current = current.left

        current = stack.pop()
        result.append(current.val)
        current = current.right

    return result

def preorderIterative(root):
    if not root:
        return []

    result = []
    stack = [root]

    while stack:
        node = stack.pop()
        result.append(node.val)

        # 오른쪽을 먼저 스택에 넣어야 왼쪽이 먼저 처리됨
        if node.right:
            stack.append(node.right)
        if node.left:
            stack.append(node.left)

    return result

BFS (Breadth-First Search) - Level Order Traversal

from collections import deque

def levelOrder(root):
    if not root:
        return []

    result = []
    queue = deque([root])

    while queue:
        level_size = len(queue)
        current_level = []

        for _ in range(level_size):
            node = queue.popleft()
            current_level.append(node.val)

            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)

        result.append(current_level)

    return result

# 예시
# 트리:     3
#          / \
#         9  20
#            / \
#           15   7
# Output: [[3], [9,20], [15,7]]

문제 1: Maximum Depth of Binary Tree (LeetCode 104)

def maxDepth(root) -> int:
    if not root:
        return 0
    return 1 + max(maxDepth(root.left), maxDepth(root.right))

# BFS 방식
def maxDepthBFS(root) -> int:
    if not root:
        return 0

    depth = 0
    queue = deque([root])

    while queue:
        depth += 1
        for _ in range(len(queue)):
            node = queue.popleft()
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)

    return depth

시간 복잡도: O(n) - 모든 노드 방문 공간 복잡도: O(h) - h는 트리 높이 (최악 O(n) for skewed tree)

문제 2: Invert Binary Tree (LeetCode 226)

def invertTree(root):
    if not root:
        return None

    # 왼쪽과 오른쪽 서브트리를 교환
    root.left, root.right = invertTree(root.right), invertTree(root.left)
    return root

# 반복 방식 (BFS)
def invertTreeBFS(root):
    if not root:
        return None

    queue = deque([root])
    while queue:
        node = queue.popleft()
        node.left, node.right = node.right, node.left

        if node.left:
            queue.append(node.left)
        if node.right:
            queue.append(node.right)

    return root

시간 복잡도: O(n) 공간 복잡도: O(n) for balanced tree, O(n) worst case

문제 3: Symmetric Tree (LeetCode 101)

트리가 대칭인지 확인하라.

def isSymmetric(root) -> bool:
    def isMirror(left, right):
        if not left and not right:
            return True
        if not left or not right:
            return False
        return (left.val == right.val and
                isMirror(left.left, right.right) and
                isMirror(left.right, right.left))

    return isMirror(root.left, root.right)

# 반복 방식
def isSymmetricIterative(root) -> bool:
    queue = deque([(root.left, root.right)])

    while queue:
        left, right = queue.popleft()

        if not left and not right:
            continue
        if not left or not right:
            return False
        if left.val != right.val:
            return False

        queue.append((left.left, right.right))
        queue.append((left.right, right.left))

    return True

문제 4: Path Sum II (LeetCode 113)

루트에서 리프까지 합이 targetSum이 되는 모든 경로를 찾아라.

def pathSum(root, targetSum: int):
    result = []

    def dfs(node, current_path, remaining):
        if not node:
            return

        current_path.append(node.val)
        remaining -= node.val

        # 리프 노드이고 합이 맞으면 경로 추가
        if not node.left and not node.right and remaining == 0:
            result.append(list(current_path))
        else:
            dfs(node.left, current_path, remaining)
            dfs(node.right, current_path, remaining)

        # 백트래킹: 현재 노드 제거
        current_path.pop()

    dfs(root, [], targetSum)
    return result

문제 5: Lowest Common Ancestor (LeetCode 236)

두 노드 p, q의 LCA(최소 공통 조상)를 찾아라.

def lowestCommonAncestor(root, p, q):
    if not root or root == p or root == q:
        return root

    left = lowestCommonAncestor(root.left, p, q)
    right = lowestCommonAncestor(root.right, p, q)

    # 양쪽에서 발견되면 현재 노드가 LCA
    if left and right:
        return root
    # 한쪽에서만 발견되면 그쪽이 LCA
    return left if left else right

# 예시
# 트리:     3
#          / \
#         5   1
#        / \ / \
#       6  2 0  8
#         / \
#        7   4
# p=5, q=1 → LCA = 3
# p=5, q=4 → LCA = 5

문제 6: Serialize and Deserialize Binary Tree (LeetCode 297) - 고난도

class Codec:
    def serialize(self, root) -> str:
        """BFS를 사용해 트리를 문자열로 직렬화"""
        if not root:
            return ""

        result = []
        queue = deque([root])

        while queue:
            node = queue.popleft()
            if node:
                result.append(str(node.val))
                queue.append(node.left)
                queue.append(node.right)
            else:
                result.append("null")

        return ",".join(result)

    def deserialize(self, data: str):
        """직렬화된 문자열에서 트리 복원"""
        if not data:
            return None

        values = data.split(",")
        root = TreeNode(int(values[0]))
        queue = deque([root])
        i = 1

        while queue:
            node = queue.popleft()

            if i < len(values) and values[i] != "null":
                node.left = TreeNode(int(values[i]))
                queue.append(node.left)
            i += 1

            if i < len(values) and values[i] != "null":
                node.right = TreeNode(int(values[i]))
                queue.append(node.right)
            i += 1

        return root

시간 복잡도: O(n) - 모든 노드 방문 공간 복잡도: O(n) - 직렬화 결과 저장

2. Binary Search Tree (BST) 패턴

BST 특성

왼쪽 서브트리의 모든 값 < 현재 노드 값
오른쪽 서브트리의 모든 값 > 현재 노드 값
Inorder 순회 시 정렬된 순서로 방문

문제 7: Validate Binary Search Tree (LeetCode 98)

def isValidBST(root) -> bool:
    def validate(node, min_val, max_val):
        if not node:
            return True

        if node.val <= min_val or node.val >= max_val:
            return False

        return (validate(node.left, min_val, node.val) and
                validate(node.right, node.val, max_val))

    return validate(root, float('-inf'), float('inf'))

# 함정: 단순히 left.val < root.val < right.val 만 체크하는 것은 틀림
# 예시:
#     5
#    / \
#   1   4
#      / \
#     3   6
# root.right.left = 3 (3 < 5 이므로 BST 위반)

문제 8: Kth Smallest Element in BST (LeetCode 230)

def kthSmallest(root, k: int) -> int:
    # Inorder 순회가 정렬된 순서이므로 k번째가 답
    count = [0]
    result = [0]

    def inorder(node):
        if not node or count[0] >= k:
            return

        inorder(node.left)
        count[0] += 1
        if count[0] == k:
            result[0] = node.val
            return
        inorder(node.right)

    inorder(root)
    return result[0]

# 반복 방식 (더 직관적)
def kthSmallestIterative(root, k: int) -> int:
    stack = []
    current = root

    while current or stack:
        while current:
            stack.append(current)
            current = current.left

        current = stack.pop()
        k -= 1
        if k == 0:
            return current.val
        current = current.right

    return -1

문제 9: Convert Sorted Array to BST (LeetCode 108)

정렬된 배열을 높이 균형 BST로 변환하라.

def sortedArrayToBST(nums: list[int]):
    def buildBST(left, right):
        if left > right:
            return None

        # 중간 값을 루트로 선택 (균형 보장)
        mid = left + (right - left) // 2
        root = TreeNode(nums[mid])
        root.left = buildBST(left, mid - 1)
        root.right = buildBST(mid + 1, right)
        return root

    return buildBST(0, len(nums) - 1)

3. Graph BFS/DFS 패턴

그래프 표현

# 인접 리스트 (권장)
graph = {
    0: [1, 2],
    1: [0, 3],
    2: [0, 4],
    3: [1],
    4: [2]
}

# 인접 행렬
matrix = [
    [0, 1, 1, 0, 0],
    [1, 0, 0, 1, 0],
    [1, 0, 0, 0, 1],
    [0, 1, 0, 0, 0],
    [0, 0, 1, 0, 0]
]

방문 처리

# DFS (재귀)
def dfs(graph, start, visited=None):
    if visited is None:
        visited = set()

    visited.add(start)
    print(start, end=' ')

    for neighbor in graph[start]:
        if neighbor not in visited:
            dfs(graph, neighbor, visited)

# BFS
def bfs(graph, start):
    visited = set([start])
    queue = deque([start])

    while queue:
        node = queue.popleft()
        print(node, end=' ')

        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)

문제 10: Number of Islands (LeetCode 200)

def numIslands(grid: list[list[str]]) -> int:
    if not grid:
        return 0

    rows, cols = len(grid), len(grid[0])
    count = 0

    def dfs(r, c):
        # 범위 벗어나거나 물이면 종료
        if r < 0 or r >= rows or c < 0 or c >= cols or grid[r][c] == '0':
            return

        # 방문 표시 (물로 변경)
        grid[r][c] = '0'

        # 4방향 탐색
        dfs(r + 1, c)
        dfs(r - 1, c)
        dfs(r, c + 1)
        dfs(r, c - 1)

    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == '1':
                count += 1
                dfs(r, c)

    return count

# 예시
# Input: grid = [
#   ["1","1","0","0","0"],
#   ["1","1","0","0","0"],
#   ["0","0","1","0","0"],
#   ["0","0","0","1","1"]
# ]
# Output: 3

시간 복잡도: O(mn) 공간 복잡도: O(mn) - 재귀 스택

문제 11: Clone Graph (LeetCode 133)

class Node:
    def __init__(self, val=0, neighbors=None):
        self.val = val
        self.neighbors = neighbors if neighbors is not None else []

def cloneGraph(node):
    if not node:
        return None

    cloned = {}  # 원본 노드 → 복제 노드 매핑

    def dfs(original):
        if original in cloned:
            return cloned[original]

        # 복제 노드 생성
        copy = Node(original.val)
        cloned[original] = copy

        # 이웃 재귀 복제
        for neighbor in original.neighbors:
            copy.neighbors.append(dfs(neighbor))

        return copy

    return dfs(node)

시간 복잡도: O(V + E) - 모든 정점과 간선 방문 공간 복잡도: O(V) - 복제 매핑 저장

문제 12: Course Schedule (LeetCode 207) - 위상 정렬

선수과목 관계가 주어질 때 모든 과목을 수강할 수 있는지 판별하라.

from collections import defaultdict, deque

def canFinish(numCourses: int, prerequisites: list[list[int]]) -> bool:
    # 그래프 구성
    graph = defaultdict(list)
    in_degree = [0] * numCourses

    for course, prereq in prerequisites:
        graph[prereq].append(course)
        in_degree[course] += 1

    # 진입 차수가 0인 노드에서 시작 (선수과목 없는 과목)
    queue = deque([i for i in range(numCourses) if in_degree[i] == 0])
    completed = 0

    while queue:
        course = queue.popleft()
        completed += 1

        for next_course in graph[course]:
            in_degree[next_course] -= 1
            if in_degree[next_course] == 0:
                queue.append(next_course)

    # 모든 과목을 완료했으면 사이클 없음
    return completed == numCourses

# DFS로 사이클 감지
def canFinishDFS(numCourses: int, prerequisites: list[list[int]]) -> bool:
    graph = defaultdict(list)
    for course, prereq in prerequisites:
        graph[prereq].append(course)

    # 상태: 0=미방문, 1=방문중, 2=완료
    state = [0] * numCourses

    def hasCycle(node):
        if state[node] == 1:  # 사이클 발견
            return True
        if state[node] == 2:  # 이미 처리됨
            return False

        state[node] = 1  # 방문 시작
        for neighbor in graph[node]:
            if hasCycle(neighbor):
                return True
        state[node] = 2  # 방문 완료
        return False

    for i in range(numCourses):
        if hasCycle(i):
            return False

    return True

문제 13: Pacific Atlantic Water Flow (LeetCode 417)

def pacificAtlantic(heights: list[list[int]]) -> list[list[int]]:
    if not heights:
        return []

    rows, cols = len(heights), len(heights[0])
    directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]

    def bfs(starts):
        visited = set(starts)
        queue = deque(starts)

        while queue:
            r, c = queue.popleft()
            for dr, dc in directions:
                nr, nc = r + dr, c + dc
                if (0 <= nr < rows and 0 <= nc < cols and
                    (nr, nc) not in visited and
                    heights[nr][nc] >= heights[r][c]):  # 역방향 탐색
                    visited.add((nr, nc))
                    queue.append((nr, nc))
        return visited

    # 태평양 (상단 + 좌측 경계)
    pacific_starts = [(0, c) for c in range(cols)] + [(r, 0) for r in range(1, rows)]
    # 대서양 (하단 + 우측 경계)
    atlantic_starts = [(rows-1, c) for c in range(cols)] + [(r, cols-1) for r in range(rows-1)]

    pacific = bfs(pacific_starts)
    atlantic = bfs(atlantic_starts)

    return [[r, c] for r, c in pacific & atlantic]

문제 14: Word Ladder (LeetCode 127)

BFS로 단어 변환 최단 경로를 구하라.

def ladderLength(beginWord: str, endWord: str, wordList: list[str]) -> int:
    word_set = set(wordList)
    if endWord not in word_set:
        return 0

    queue = deque([(beginWord, 1)])
    visited = {beginWord}

    while queue:
        word, steps = queue.popleft()

        for i in range(len(word)):
            for c in 'abcdefghijklmnopqrstuvwxyz':
                new_word = word[:i] + c + word[i+1:]

                if new_word == endWord:
                    return steps + 1

                if new_word in word_set and new_word not in visited:
                    visited.add(new_word)
                    queue.append((new_word, steps + 1))

    return 0

# 예시
# beginWord = "hit", endWord = "cog"
# wordList = ["hot","dot","dog","lot","log","cog"]
# Output: 5 (hit→hot→dot→dog→cog)

시간 복잡도: O(M^2 _ N) - M은 단어 길이, N은 단어 수 공간 복잡도: O(M^2 _ N)

4. Union Find (Disjoint Set) 패턴

구현

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))  # 각 노드의 부모
        self.rank = [0] * n           # 트리 높이

    def find(self, x):
        # Path Compression
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    def union(self, x, y):
        px, py = self.find(x), self.find(y)
        if px == py:
            return False  # 이미 같은 집합

        # Union by Rank
        if self.rank[px] < self.rank[py]:
            px, py = py, px
        self.parent[py] = px
        if self.rank[px] == self.rank[py]:
            self.rank[px] += 1
        return True

    def connected(self, x, y):
        return self.find(x) == self.find(y)

문제 15: Number of Connected Components (LeetCode 323)

def countComponents(n: int, edges: list[list[int]]) -> int:
    uf = UnionFind(n)
    components = n

    for u, v in edges:
        if uf.union(u, v):
            components -= 1  # 두 컴포넌트가 합쳐지면 감소

    return components

문제 16: Redundant Connection (LeetCode 684)

트리에 하나의 중복 간선이 추가되었을 때, 그 간선을 찾아라.

def findRedundantConnection(edges: list[list[int]]) -> list[int]:
    n = len(edges)
    uf = UnionFind(n + 1)

    for u, v in edges:
        if not uf.union(u, v):
            return [u, v]  # 이미 연결된 경우 → 중복 간선

    return []

문제 17: Accounts Merge (LeetCode 721)

def accountsMerge(accounts: list[list[str]]) -> list[list[str]]:
    email_to_id = {}   # 이메일 → ID
    email_to_name = {} # 이메일 → 이름

    # 모든 이메일에 고유 ID 부여
    for i, account in enumerate(accounts):
        name = account[0]
        for email in account[1:]:
            if email not in email_to_id:
                email_to_id[email] = len(email_to_id)
            email_to_name[email] = name

    uf = UnionFind(len(email_to_id))

    # 같은 계정의 이메일들을 Union
    for account in accounts:
        first_email = account[1]
        first_id = email_to_id[first_email]
        for email in account[2:]:
            uf.union(first_id, email_to_id[email])

    # 같은 그룹의 이메일들을 모음
    from collections import defaultdict
    groups = defaultdict(list)
    for email, eid in email_to_id.items():
        root = uf.find(eid)
        groups[root].append(email)

    result = []
    for root, emails in groups.items():
        name = email_to_name[emails[0]]
        result.append([name] + sorted(emails))

    return result

5. Shortest Path 알고리즘

Dijkstra's Algorithm

음수 가중치가 없는 그래프에서 단일 출발점 최단 경로를 구합니다.

import heapq
from collections import defaultdict

def dijkstra(graph: dict, start: int) -> dict:
    distances = {node: float('inf') for node in graph}
    distances[start] = 0
    priority_queue = [(0, start)]  # (거리, 노드)

    while priority_queue:
        current_dist, current_node = heapq.heappop(priority_queue)

        # 더 짧은 경로가 이미 있으면 스킵
        if current_dist > distances[current_node]:
            continue

        for neighbor, weight in graph[current_node]:
            distance = current_dist + weight

            if distance < distances[neighbor]:
                distances[neighbor] = distance
                heapq.heappush(priority_queue, (distance, neighbor))

    return distances

# 예시
graph = {
    0: [(1, 4), (2, 1)],
    1: [(3, 1)],
    2: [(1, 2), (3, 5)],
    3: []
}
# distances from 0: {0: 0, 1: 3, 2: 1, 3: 4}

시간 복잡도: O((V + E) log V) 공간 복잡도: O(V)

문제 18: Network Delay Time (LeetCode 743)

def networkDelayTime(times: list[list[int]], n: int, k: int) -> int:
    graph = defaultdict(list)
    for u, v, w in times:
        graph[u].append((v, w))

    distances = {i: float('inf') for i in range(1, n + 1)}
    distances[k] = 0
    pq = [(0, k)]

    while pq:
        dist, node = heapq.heappop(pq)

        if dist > distances[node]:
            continue

        for neighbor, weight in graph[node]:
            new_dist = dist + weight
            if new_dist < distances[neighbor]:
                distances[neighbor] = new_dist
                heapq.heappush(pq, (new_dist, neighbor))

    max_dist = max(distances.values())
    return max_dist if max_dist != float('inf') else -1

# 예시
# times = [[2,1,1],[2,3,1],[3,4,1]], n=4, k=2
# Output: 2

문제 19: Cheapest Flights Within K Stops (LeetCode 787)

Bellman-Ford 변형으로 k번 이하 경유지로 최저 비용을 구합니다.

def findCheapestPrice(n: int, flights: list[list[int]], src: int, dst: int, k: int) -> int:
    # Bellman-Ford: k+1번 릴랙세이션
    prices = [float('inf')] * n
    prices[src] = 0

    for i in range(k + 1):
        temp = prices.copy()  # 현재 단계 결과를 분리

        for u, v, w in flights:
            if prices[u] != float('inf') and prices[u] + w < temp[v]:
                temp[v] = prices[u] + w

        prices = temp

    return prices[dst] if prices[dst] != float('inf') else -1

# 예시
# n=3, flights=[[0,1,100],[1,2,100],[0,2,500]], src=0, dst=2, k=1
# Output: 200 (0→1→2)

6. FAANG 기업별 트리/그래프 출제 경향

Google

Google은 그래프 문제를 매우 자주 출제합니다.

자주 출제: 그래프 탐색, 위상 정렬, 최단 경로
핵심: 효율적인 알고리즘 선택과 복잡도 분석
예시 문제: Course Schedule II, Word Ladder, Alien Dictionary

Meta (Facebook)

Meta는 Tree Traversal과 LCA 문제를 선호합니다.

자주 출제: Binary Tree, LCA, Serialize/Deserialize
핵심: 재귀와 반복 두 방식 모두 구현 가능
예시 문제: Binary Tree Right Side View, Vertical Order Traversal

Amazon

Amazon은 BFS/최단 경로 문제를 많이 출제합니다.

자주 출제: Number of Islands, BFS 변형, Union Find
핵심: 실용적이고 효율적인 해법
예시 문제: Rotting Oranges, Find if Path Exists in Graph

7. 연습 문제 퀴즈

퀴즈 1: 이진 트리의 지름 (Diameter)

이진 트리에서 임의의 두 노드 사이의 최장 경로 길이(간선 수)를 구하라. 경로가 루트를 통과하지 않아도 됩니다.

정답: DFS로 각 노드에서 왼쪽/오른쪽 최대 깊이의 합을 계산하고 전역 최대값을 업데이트합니다.

설명:

def diameterOfBinaryTree(root) -> int:
    max_diameter = [0]

    def depth(node):
        if not node:
            return 0
        left_depth = depth(node.left)
        right_depth = depth(node.right)
        # 현재 노드를 지나는 경로의 지름
        max_diameter[0] = max(max_diameter[0], left_depth + right_depth)
        return 1 + max(left_depth, right_depth)

    depth(root)
    return max_diameter[0]

퀴즈 2: 그래프에서 사이클 감지

방향 그래프 graph = {0: [1], 1: [2], 2: [0], 3: [4], 4: []}에서 사이클이 있는가?

정답: Yes (0 → 1 → 2 → 0)

설명: DFS와 색상 마킹(0=미방문, 1=방문중, 2=완료)을 사용합니다. 방문 중인 노드를 다시 만나면 사이클입니다.

def hasCycle(graph):
    state = {}

    def dfs(node):
        if state.get(node) == 1:
            return True   # 사이클
        if state.get(node) == 2:
            return False  # 이미 처리

        state[node] = 1
        for neighbor in graph.get(node, []):
            if dfs(neighbor):
                return True
        state[node] = 2
        return False

    return any(dfs(node) for node in graph if node not in state)

퀴즈 3: BST에서 두 노드 값의 합 찾기

BST와 타겟 k가 주어질 때 두 노드 값의 합이 k가 되는 경우가 있는지 판별하라.

정답: Inorder 순회로 정렬된 값들을 얻은 후 Two Pointers를 적용합니다.

설명:

def findTarget(root, k: int) -> bool:
    def inorder(node):
        if not node:
            return []
        return inorder(node.left) + [node.val] + inorder(node.right)

    nums = inorder(root)
    left, right = 0, len(nums) - 1

    while left < right:
        total = nums[left] + nums[right]
        if total == k:
            return True
        elif total < k:
            left += 1
        else:
            right -= 1
    return False

퀴즈 4: 섬의 최대 넓이

이진 그리드에서 1로 연결된 섬 중 가장 큰 섬의 넓이를 구하라.

정답: DFS/BFS로 각 섬의 넓이를 계산하고 최대값을 반환합니다.

설명:

def maxAreaOfIsland(grid):
    rows, cols = len(grid), len(grid[0])

    def dfs(r, c):
        if r < 0 or r >= rows or c < 0 or c >= cols or grid[r][c] == 0:
            return 0
        grid[r][c] = 0  # 방문 표시
        return 1 + dfs(r+1,c) + dfs(r-1,c) + dfs(r,c+1) + dfs(r,c-1)

    return max(dfs(r, c) for r in range(rows) for c in range(cols) if grid[r][c])

퀴즈 5: 최소 스패닝 트리 - Kruskal 알고리즘

Union Find를 이용해 n개의 도시를 최소 비용으로 연결하는 알고리즘을 구현하라. (Min Cost to Connect All Points, LeetCode 1584)

정답: 모든 간선을 비용 오름차순으로 정렬 후, Union Find로 사이클 없이 간선을 추가합니다.

설명:

def minCostConnectPoints(points):
    n = len(points)
    # 모든 간선 생성 (맨해튼 거리)
    edges = []
    for i in range(n):
        for j in range(i + 1, n):
            dist = abs(points[i][0] - points[j][0]) + abs(points[i][1] - points[j][1])
            edges.append((dist, i, j))

    edges.sort()
    uf = UnionFind(n)
    total_cost = 0
    edges_used = 0

    for cost, u, v in edges:
        if uf.union(u, v):
            total_cost += cost
            edges_used += 1
            if edges_used == n - 1:
                break

    return total_cost

마무리

트리와 그래프는 FAANG 인터뷰에서 가장 다양한 패턴이 등장하는 분야입니다. 특히:

DFS/BFS 선택: 최단 경로 → BFS, 모든 경로 탐색 → DFS
트리 문제: 재귀가 자연스러운 경우가 많음, 반복도 준비
그래프 문제: visited 처리를 항상 명확히 하기
Union Find: 연결성 문제에서 강력한 도구

추천 LeetCode 목록:

Easy: Maximum Depth, Invert Tree, Symmetric Tree
Medium: Course Schedule, Number of Islands, LCA, BFS/DFS 변형
Hard: Serialize/Deserialize, Word Ladder II, Alien Dictionary