연습 문제

그래프 탐색 문제는 대부분 "무엇이 정점이고 무엇이 간선인가"를 정하는 순간 절반이 풀립니다. 아래 네 문제는 코딩 테스트에 자주 나오는 유형을 이 문서를 위해 새로 만든 것입니다. 먼저 스스로 풀어 본 뒤 풀이를 확인하세요.

문제 1. 창고 로봇의 최단 이동

창고 지도가 문자열 목록으로 주어집니다. S는 로봇의 출발점, E는 목적지, #은 선반(지나갈 수 없음), .은 빈 칸입니다. 로봇은 한 번에 상하좌우로 한 칸 움직입니다. 목적지까지 최소 몇 번 움직여야 하는지 구하고, 갈 수 없으면 -1을 돌려주세요.

접근: 칸이 정점, 이웃한 빈 칸 사이가 간선인 격자 그래프입니다. 모든 이동 비용이 1이므로 BFS로 처음 E에 도달한 거리가 답입니다.

from collections import deque

def min_steps(grid):
    rows, cols = len(grid), len(grid[0])
    start = next((r, c) for r in range(rows) for c in range(cols) if grid[r][c] == "S")
    dist = {start: 0}
    queue = deque([start])
    while queue:
        r, c = queue.popleft()
        if grid[r][c] == "E":
            return dist[(r, c)]
        for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
            nr, nc = r + dr, c + dc
            if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] != "#" and (nr, nc) not in dist:
                dist[(nr, nc)] = dist[(r, c)] + 1
                queue.append((nr, nc))
    return -1

print(min_steps(["S.#.", "..#E", "...."]))  # 6

선반 때문에 맨 아래 줄로 돌아가야 하므로 맨해튼 거리 4가 아니라 6이 나옵니다.

문제 2. 서버 묶음 세기

서버 n대와 케이블 목록 (a, b)가 주어집니다. 케이블로 직접 또는 간접적으로 이어진 서버는 같은 묶음입니다. 묶음의 개수와 가장 큰 묶음의 서버 수를 구하세요.

접근: 연결 요소 문제입니다. 아직 방문하지 않은 서버마다 탐색을 한 번 시작하고, 탐색에서 만난 서버 수를 셉니다. 재귀 한도를 피하려고 스택을 씁니다.

def server_groups(n, cables):
    adj = [[] for _ in range(n)]
    for a, b in cables:
        adj[a].append(b)
        adj[b].append(a)
    seen = [False] * n
    groups, largest = 0, 0
    for s in range(n):
        if seen[s]:
            continue
        groups += 1
        seen[s] = True
        stack, size = [s], 0
        while stack:
            u = stack.pop()
            size += 1
            for v in adj[u]:
                if not seen[v]:
                    seen[v] = True
                    stack.append(v)
        largest = max(largest, size)
    return groups, largest

print(server_groups(7, [(0, 1), (1, 2), (3, 4)]))  # (4, 3)

문제 3. 모듈 빌드 순서

모듈마다 먼저 빌드되어야 하는 모듈 목록이 사전으로 주어집니다. 모든 모듈을 빌드할 수 있는 순서를 돌려주되, 동시에 빌드할 수 있는 모듈이 여럿이면 이름이 빠른 것부터 고릅니다. 순환 의존이 있으면 None을 돌려주세요.

접근: "A가 B보다 먼저"는 간선 A→B이므로 위상 정렬입니다. Kahn 알고리즘의 큐를 힙으로 바꾸면 준비된 모듈 중 이름이 가장 빠른 것을 꺼낼 수 있습니다.

import heapq

def build_order(deps):
    indeg = {m: 0 for m in deps}
    users = {m: [] for m in deps}
    for module, needs in deps.items():
        for need in needs:
            users[need].append(module)
            indeg[module] += 1
    ready = [m for m, d in indeg.items() if d == 0]
    heapq.heapify(ready)
    order = []
    while ready:
        m = heapq.heappop(ready)
        order.append(m)
        for user in users[m]:
            indeg[user] -= 1
            if indeg[user] == 0:
                heapq.heappush(ready, user)
    return order if len(order) == len(deps) else None

deps = {"app": ["ui", "net"], "ui": ["core"], "net": ["core"], "core": [], "log": []}
print(build_order(deps))                      # ['core', 'log', 'net', 'ui', 'app']
print(build_order({"a": ["b"], "b": ["a"]}))  # None

힙 때문에 시간은 O((V + E) log V)가 됩니다. 순서가 아무거나 괜찮다면 deque로 충분합니다.

문제 4. 동시에 퍼지는 신호

격자에 중계기 R가 여러 개 있고, 신호는 1분마다 상하좌우의 빈 칸 .으로 한 칸씩 퍼집니다. #은 벽입니다. 모든 빈 칸에 신호가 닿는 데 걸리는 시간을 구하고, 끝까지 닿지 않는 칸이 있으면 -1을 돌려주세요.

접근: 출발점이 여럿인 다중 출발 BFS입니다. 모든 R를 거리 0으로 큐에 함께 넣고 시작하면, 각 칸까지의 거리가 "가장 가까운 중계기까지의 거리"가 됩니다. 중계기마다 BFS를 따로 돌리면 훨씬 느립니다.

from collections import deque

def spread_time(grid):
    rows, cols = len(grid), len(grid[0])
    dist = [[-1] * cols for _ in range(rows)]
    queue = deque()
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == "R":
                dist[r][c] = 0
                queue.append((r, c))
    while queue:
        r, c = queue.popleft()
        for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
            nr, nc = r + dr, c + dc
            if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == "." and dist[nr][nc] == -1:
                dist[nr][nc] = dist[r][c] + 1
                queue.append((nr, nc))
    cells = [dist[r][c] for r in range(rows) for c in range(cols) if grid[r][c] == "."]
    return -1 if -1 in cells else max(cells, default=0)

print(spread_time(["R..#", "...#", "#..R"]))  # 2

정리

격자 최단 거리는 BFS, 묶음 세기는 연결 요소, 순서 정하기는 위상 정렬, 여러 출발점은 다중 출발 BFS로 바꿔 생각하면 됩니다. 문제를 읽을 때 정점과 간선, 가중치 유무, 방향 유무를 먼저 적어 보는 습관이 가장 큰 도움이 됩니다.