개요

오늘 과제로 받은 벽돌 깨기는 버그 하나를 고치면 다음 버그가 나왔다.. 그렇게 고친 게 여섯 개였고, 제일 오래 붙잡은 건 중력 처리에서 난 무한루프였다. 그중 하나가 보드 복사였다. Python - < 8 >의 숫자 만들기에서도 분기마다 copy()로 넘겼는데, 2차원 보드에서는 얕은 복사라 다른 분기의 보드까지 같이 지워졌다.

수업은 오전에 서로소 집합, 오후에 최소 신장 트리를 배웠고, 강의가 끝난 뒤 AI가 던지는 질문에 답하면서 이해한 걸 확인했다. 사이클은 이론 정리 - < 이진 탐색, BST, 그래프 탐색 >에서 visited로 피해 다니던 대상이었는데, Kruskal은 탐색 없이 대표자 비교만으로 막는다. 배운 순서대로 적어보겠다!

  • 서로소 집합: union을 루트끼리 이어야 하는 이유와 창용 마을 무리 세기
  • 최소 신장 트리: 대표자가 같으면 사이클인 이유, Prim의 visited 검사, 밀집 그래프에서 더 빠른 쪽
  • MST와 최단 경로: 슬라이드의 “Prim은 음수 불가” 확인, 던전 복도 문제
  • 벽돌 깨기: 무한루프부터 얕은 복사까지 버그 여섯 개

서로소 집합 — union은 루트끼리

서로소 집합은 교집합이 없는 집합들을 다루고, 집합마다 대표자 하나를 둔다. 두 원소가 같은 집합인지는 대표자가 같은지로 판정한다.

트리로 표현하면 자식이 부모를 가리키고 루트가 대표자다. p[i] = i의 부모 배열 하나로 저장할 수 있다. 연산 순서에 따라 트리가 한 줄로 늘어지면 find_set이 O(N)이 되는데, 이걸 막는 최적화가 두 가지 있다.

  • Path Compression: find_set이 지나간 노드의 부모를 루트로 바꿔 다음 탐색을 짧게 만든다
  • Union by Rank: rank가 낮은 트리를 높은 트리 밑에 붙이고, rank가 같을 때만 +1 한다

최적화 전 union이 집합을 쪼갠다

강의자료의 최적화 전 union은 p[y] = px처럼 원소 y 자체의 부모를 바꾸는 형태였다. 손으로 따라가 보니 이러면 집합이 쪼개졌다.

  1. make_set(1), make_set(2), make_set(3)
  2. union(2, 3): p[3] = 2, 집합은 {2, 3}
  3. union(1, 3): px = 1이고 p[3] = 1
  4. 3이 1 밑으로 옮겨 가면서 2는 혼자 남는다. {1, 3}과 {2}

y가 속한 트리의 루트 py를 옮겨야( p[py] = px ) y와 같은 집합의 원소가 전부 함께 따라온다.

창용 마을 무리의 개수

문제. ( SWEA 7465 ) 창용 마을 사람 N명 사이의 아는 관계 M개가 주어진다. 서로 알거나 몇 사람을 거쳐 알면 같은 무리다. 무리의 개수를 구한다.

  • 입력: 테스트케이스 수 T. 케이스마다 N M, 이후 M줄에 서로 아는 두 사람의 번호
  • 제약: N ≤ 100, 사람 번호는 1부터 N
  • 출력: #테스트케이스번호 무리의개수 
T = int(input())


def find_set(x):
    if parents[x] != x:
        # 탐색 과정에서 최적화
        parents[x] = find_set(parents[x])
    return parents[x]


def union_set(x, y):
    px = find_set(x)
    py = find_set(y)

    if px == py: return

    # 랭크 최적화로 트리 깊이 조절
    if rank[px] > rank[py]:
        parents[py] = px
    elif rank[px] < rank[py]:
        parents[px] = py
    else:
        parents[py] = px
        rank[px] += 1


for test_case in range(1, T + 1):
    N, M = map(int, input().split())
    parents = [i for i in range(N + 1)]
    rank = [0] * (N + 1)

    for input_x, input_y in [list(map(int, input().split())) for _ in range(M)]:
        union_set(input_x, input_y)

    # parents 탐색해가며 마무리 정리
    [find_set(person) for person in range(N + 1)]

    # 0 제외
    print(f"#{test_case} {len(set(parents)) - 1}")

Path Compression과 Union by Rank를 둘 다 넣었고, union_set은 find_set으로 찾은 루트끼리 잇는다.

무리 수는 모든 원소에 find_set을 한 번씩 불러 경로를 전부 압축한 다음 셌다. 압축이 끝나면 parents[x]가 곧 루트라서 set(parents)의 크기가 서로 다른 루트의 수다. 0번은 쓰지 않는 칸인데 자기 자신만 든 집합으로 잡히니 -1 했다.

union이 두 집합을 합칠 때마다 무리 수를 1씩 줄이는 방법도 있다. N에서 시작해 px != py일 때만 빼면 마지막 압축 단계가 필요 없다.

최소 신장 트리

신장 트리는 정점 n개를 간선 n−1개로 모두 잇는 트리고, 최소 신장 트리( MST )는 그중 간선 가중치 합이 가장 작은 트리다. 구하는 방법은 두 가지를 배웠다.

  • Kruskal: 간선을 가중치 오름차순으로 정렬하고, 두 끝점의 대표자가 다를 때만 채택한다. 사이클 검사를 서로소 집합이 맡는다
  • Prim: 시작 정점 하나에서 출발해 우선순위 큐로 가장 싼 간선을 꺼내며, 방문하지 않은 정점을 하나씩 붙인다

대표자가 같으면 왜 사이클인가

Kruskal의 흐름을 줄이면 이렇다.

edges.sort(key=lambda e: e[2])  # 가중치 오름차순
mst = []
for u, v, w in edges:
    if find_set(u) == find_set(v):  # 대표자가 같으면 사이클이 생기므로 버림
        continue
    union_set(u, v)  # 두 집합을 합치고
    mst.append((u, v, w))  # 같은 순간에 간선을 채택

같은 집합에 속한 두 정점 사이에는 이미 선택한 간선들로만 이루어진 경로가 있다.

위 코드에서 union_set과 mst.append가 항상 짝으로 일어나기 때문에 성립한다. 서로소 집합 하나는 언제나 “선택한 간선으로 이어진 연결 요소”와 같고, 이렇게 실행 내내 유지되는 성질을 불변식( invariant )이라고 부른다. 이미 경로가 있는 u, v 사이에 간선을 더하면 u에서 v로 가는 두 번째 길이 생기고, 그게 사이클이다.

이 불변식 덕분에 Kruskal은 그래프를 탐색하지 않고 find_set 두 번으로 사이클을 판정한다.

최소 신장 트리 — 힙 Prim

문제. ( SWEA [파이썬 S/W 문제해결 구현] 7일차 - 최소 신장 트리 ) 0번부터 V번까지의 노드와 가중치가 있는 무방향 간선 E개가 주어진다. 모든 노드를 잇는 트리 중 간선 가중치 합의 최솟값을 구한다.

  • 입력: 테스트케이스 수 T. 케이스마다 V E, 이후 E줄에 n1 n2 w
  • 제약: V ≤ 1,000, E ≤ 1,000,000
  • 출력: #테스트케이스번호 가중치합 
import heapq

T = int(input())

for test_case in range(1, T + 1):
    # V = 마지막 노드번호, E = 간선의 개수
    V, E = map(int, input().split())

    adj_list = {v: [] for v in range(V + 1)}
    edges = [list(map(int, input().split())) for _ in range(E)]
    for n1, n2, w in edges:
        adj_list[n1].append((n2, w))
        adj_list[n2].append((n1, w))

    total_sum = 0
    visited = set()
    min_heap = [[w, 0, e] for e, w in adj_list[0]]
    heapq.heapify(min_heap)
    visited.add(0)

    while min_heap:
        weight, start, end = heapq.heappop(min_heap)
        if end in visited: continue

        visited.add(end)
        total_sum += weight

        # 다음 미탐색 방향 삽입
        for adj_start, ajd_weight in adj_list[end]:
            if adj_start in visited: continue
            heapq.heappush(min_heap, [ajd_weight, end, adj_start])

    print(f'#{test_case} {total_sum}')

정점 0에서 출발하는 힙 Prim이다. 힙에서 꺼낸 간선의 도착 정점이 이미 방문됐으면 버린다.

if end in visited: continue는 왜 필요한가

같은 정점으로 가는 간선이 힙에 여러 개 들어갈 수 있다. 0−6( 51 )과 2−6( 25 )이 함께 힙에 있으면 25가 먼저 나와 6을 방문 처리하고, 나중에 나오는 51은 쓸모가 없어진다.

여기에 “이미 시작 지점으로 쓴 정점”도 따로 걸러야 하는 경우로 꼽았는데, 별개의 경우는 아니었다. 최초 시작 정점 0은 push할 때 visited로 걸러져 힙에 들어가지 않고, 나중에 확장 기준이 된 정점은 위와 같은 원리로 걸린다. 한 줄로 줄이면 push할 때는 미방문이었는데 pop할 때는 방문된 간선을 버리는 검사다.

그럼 중복을 쌓지 말고 힙 안의 값을 고치면 되지 않을까? 힙은 “부모 ≤ 자식”만 보장해서 특정 원소를 찾으려면 전체를 훑어야 하고 O(n)이 든다. 그래서 Python heapq에서는 중복을 push하고 꺼낼 때 버리는 방식( lazy deletion )을 쓴다. push는 O(log n), 꺼낼 때 검사는 O(1)이다. 원소 위치를 따로 추적하는 indexed priority queue를 쓰면 값 갱신( decrease-key )을 O(log n)에 할 수도 있다.

밀집 그래프에서는 무엇이 빠른가

  1. 간선 수는 E ≤ V(V−1)/2 < V²
  2. log는 단조 증가라 양변에 씌우면 log E < log V² = 2 log V. V = 1,000이면 log₂V ≈ 10, log₂V² ≈ 20으로, 엄청나던 차이가 2배로 줄어든다
  3. Big-O는 상수배를 무시하니 O(E log E) = O(E log V). 강의 자료에서 Prim에 대해 “O(E log E) or O(E log V)”가 같이 적혀 있던 이유다
  4. 연결 그래프는 E ≥ V − 1이라 힙 Prim의 O((V+E) log V)도 O(E log V)

Kruskal과 힙 Prim은 같은 등급이다.

배열로 구현한 Prim은 계산이 다르다. 단계마다 key가 가장 작은 정점을 배열에서 고르는 데 O(V)이고 이걸 V−1번 하며, key 갱신은 전체 O(E)라서 O(V² + E)다. 밀집 그래프( E ≈ V² )에서는 배열 Prim이 O(V²), 힙 Prim이 O(V² log V)로 log V배 차이가 난다.

처음엔 밀집 그래프에서 배열 Prim 쪽이 더 크다고 답했는데, 이 문제 조건( V = 1,000, E = 1,000,000 )을 넣어 곱해보니 배열 Prim이 약 200만, 힙 Prim이 약 1,000만이라 결론을 고쳤다.

“Prim은 밀집 그래프에 유리하다”는 말은 배열 Prim일 때 성립한다. 희소 그래프( E ≈ V )에서는 힙 Prim이나 Kruskal의 O(E log V)가 유리하다. 고를 때는 E가 V²에 가까운지, V에 가까운지를 본다.

서로소 집합 최적화가 없으면

같은 조건에서 Kruskal을 쓰면 서로소 집합 최적화가 얼마나 필요할까. 최적화 없이 트리가 한 줄이면 find_set 한 번에 O(V)이고, Kruskal은 간선마다 두 번씩, 총 2E번 find_set을 부른다.

처음엔 한 번의 비용인 1,000을 답했다가 호출 횟수를 곱해 고쳤다. 2 × 1,000,000 × 1,000 = 20억이다. Python이 초당 10⁷번쯤 연산한다고 어림하면 약 200초로, 제한 2초에는 어림도 없다.

적용 find_set 1회 총 비용
없음 O(V) ≈ 1,000 약 20억
Rank만 O(log V) ≈ 10 약 2,000만
Path Compression + Rank O(α(V)), 사실상 상수 수백만 수준

α는 역 아커만 함수로, 현실적인 입력 크기에서는 4를 넘지 않는다.

MST와 최단 경로

Prim은 음수 가중치를 처리하지 못한다?

강의 슬라이드에 “Prim은 음의 가중치를 처리할 수 없음”이라는 서술이 있었다. 처음엔 맞는지 판단하지 못했지만, 코드 모양은 비슷한데 음수에서 깨지는 알고리즘을 묻는 질문에는 다익스트라를 떠올렸다.

작은 그래프로 확인했다. 간선은 A−B( −5 ), A−C( 2 ), B−C( 3 ).

  • A에서 시작한 Prim: A−B( −5 )를 고르고, 남은 A−C( 2 )와 B−C( 3 ) 중 A−C를 골라 합 −3
  • 가능한 신장 트리 세 개를 모두 나열하면 합이 −3, −2, 5로 최솟값 −3

결과가 같다. Prim은 간선끼리 대소 비교만 하고 부호를 따지거나 값을 누적하지 않기 때문이다.

다익스트라와 갈리는 지점은 힙에 넣는 값이다. 다익스트라는 누적 거리를 넣고 “한 번 꺼낸 정점의 거리는 확정”이라는 전제를 쓰는데, 이 전제는 음수 간선이 없어야 성립한다. Prim은 간선 하나의 가중치만 비교하니 이 전제가 필요 없고, 슬라이드의 서술은 틀린 것이었다.

모든 간선에 10을 더하면

모든 간선에 +10을 해도 MST는 바뀌지 않는다. 간선끼리의 대소 관계가 그대로라 알고리즘이 고르는 순서가 같다. 정의로 봐도 신장 트리는 모두 간선이 V−1개라서, 모든 후보의 합이 똑같이 10(V−1)씩 늘고 순위가 유지된다.

다익스트라에 같은 변환을 써서 음수 간선을 없앨 수 있냐는 질문에는 음수 사이클을 근거로 안 된다고 답했다. 결론은 맞았지만 질문과 다른 지점을 짚었고, 표를 채워보고 이유를 확인했다.

경로 간선 수 원래 합 +10 후
S → T 1 5 15
S → A → T 2 4 24

원래 최단은 S→A→T였는데 변환하고 나면 S→T가 최단이 된다. 경로마다 간선 수가 달라서 늘어나는 양도 달랐다. 그래서 음수 간선이 있는 최단 경로는 벨만-포드처럼 다른 알고리즘으로 푼다.

던전 복도는 MST로

절차적 던전에서 방 20개를 복도로 연결하면서 복도 총길이를 최소로 하려면 무엇을 써야 할까. 처음엔 다익스트라라고 답했는데 오답이었다. S−A( 4 ), S−B( 4 ), A−B( 1 ) 그래프로 계산해 보면 두 트리가 다르게 나온다.

  간선 복도 총길이 S→B 거리
최단 경로 트리 S−A, S−B 8 4
MST A−B, S−A 5 5

MST는 간선 가중치 합, 깔아야 할 복도 총량을 최소로 만든다. 최단 경로 트리는 시작점에서 각 정점까지의 거리를 최소로 만든다. 이 예시처럼 한 트리가 두 목표를 동시에 최소로 만들지 못할 수 있다.

MST에는 순환이 없으니, 순환 경로를 넣고 싶으면 간선을 다시 더해야 한다. 어떤 간선을 골라야 할까? Kruskal에서 버려진 간선은 두 끝점 사이에 이미 경로가 있던 간선이라, MST에 하나 더하면 사이클이 정확히 하나 생긴다. 원래 그래프의 아무 간선이나 고르면 이미 MST에 있는 간선을 다시 뽑아 복도만 겹칠 수 있다.

V−1개를 채우자마자 멈추는 Kruskal이라면 검사하지 않고 끝난 간선도 남는다. 이 간선들도 같은 원리로 사이클을 만드니, 후보는 정확히 MST에 포함되지 않은 모든 간선이다.

이 흐름은 게임에도 쓰였다. TinyKeep 개발자가 공개한 던전 생성 설명에서는 방 중심점으로 들로네 삼각분할 그래프를 만들고 MST를 구한 뒤, MST에 들지 않은 간선 중 15% 정도를 다시 넣어 루프를 만든다.

벽돌 깨기 — 버그 여섯 개

문제. ( SWEA 5656, 수업 과제 ) W × H 칸에 1~9가 적힌 벽돌이 쌓여 있다. 구슬을 N번 위에서 떨어뜨릴 수 있고, 구슬은 떨어진 열의 맨 위 벽돌을 깬다. 숫자가 k인 벽돌이 깨지면 상하좌우로 k−1칸 안의 벽돌도 함께 깨지고, 그 벽돌들도 연쇄로 터진다. 폭발이 끝나면 빈칸 위의 벽돌이 아래로 떨어진다. 남는 벽돌 수의 최솟값을 구한다.

  • 입력: 테스트케이스 수 T. 케이스마다 N W H, 이후 H줄에 W개 숫자( 0은 빈칸 )
  • 제약: 1 ≤ N ≤ 4, 2 ≤ W ≤ 12, 2 ≤ H ≤ 15
  • 출력: #테스트케이스번호 남은벽돌수

스택으로 DFS를 돌렸다. 상태 하나는 ( 쏠 위치, 남은 구슬 수, 남은 벽돌 수, 보드 )이고, 상태를 꺼낼 때마다 이 순서로 처리했다.

  1. 보드를 복사한다
  2. 연쇄 폭발을 처리한다
  3. 중력을 적용한다
  4. 각 열의 맨 위 벽돌을 다음 발사 위치로 push한다

틀은 이렇게 잡았는데, 돌릴 때마다 다른 곳에서 문제가 났다. #1 무한루프를 제일 오래 붙잡고 있었고, 그 뒤로 막히는 곳은 AI에게 코드를 보여주며 원인을 찾았다.

# 증상 원인 수정
1 무한루프 중력 루프에서 빈칸에 빈칸을 끌어와도 0이 유지돼 while not cur_board[i][j]가 끝나지 않음. 값을 아래( i+1 )에서 끌어오는 방향도 반대 열마다 아래에서 위로 훑고, 빈칸이면 위쪽( ni 감소 )에서 가장 가까운 벽돌을 끌어옴. ni > 0 검사 후 감소시켜 행 0까지 탐색
2 다른 분기의 보드가 오염 pre_board.copy()는 바깥 리스트만 복사하는 얕은 복사 copy.deepcopy(pre_board)
3 분기마다 시작 위치가 자기 보드를 반영하지 않음 check(board) 안에서 매개변수 대신 전역 matrix를 참조 board로 교체
4 폭발 범위 이상, IndexError 가능 경계 검사에 구슬 수 N 사용, push 좌표 오타 (ny, ny) 행은 H, 열은 W로 검사하고 (nx, ny) push
5 구슬이 남았는데 벽돌이 다 깨지면 결과 0이 기록되지 않음 다음 시작 위치가 모두 빈칸이라 push가 없음 매 발사 직후 min_count = min(min_count, cur_bricks)로 갱신, bricks <= 0이면 종료
6 맨 위 벽돌이 행 0이면 잘못된 행을 가리킴 기본값 (0, 0)이 “행 0에서 찾음”과 구별되지 않음 기본값을 (-1, -1)로 바꾸고 >= 0으로 판정

#2는 2차원 리스트라서 생긴 문제다. copy()는 바깥 리스트만 새로 만들고 안쪽 행 리스트는 그대로 공유하니, 한 분기에서 칸을 지우면 다른 분기의 보드에서도 지워진다.

# 복사 딥카피 변경
cur_board = copy.deepcopy(pre_board)

연쇄 폭발은 터질 칸을 스택에 쌓아 처리했다. range(dist)의 i = 0은 자기 자신이라, 벽돌 숫자보다 하나 적은 칸까지 퍼진다.

# 연쇄 폭발
while bombs:
    x, y = bombs.pop()
    dist = cur_board[x][y]
    # 이미 비어있는 부분 무시
    if not dist: continue

    # 폭발처리
    cur_board[x][y] = 0
    for dx, dy in dxy:
        for i in range(dist):
            nx, ny = x + (dx * i), y + (dy * i)

            if 0 > nx or H <= nx or 0 > ny or W <= ny: continue
            if not cur_board[nx][ny]: continue
            bombs.append((nx, ny))

#1을 고친 중력이다. ni > 0이 있어서 위쪽 끝에 닿으면 루프가 반드시 끝난다.

# 중력 적용
for j in range(W):
    for i in range(H)[::-1]:
        if cur_board[i][j]: continue
        ni = i
        while not cur_board[i][j] and ni > 0:
            ni -= 1
            cur_board[i][j] = cur_board[ni][j]
            cur_board[ni][j] = 0

#3과 #6을 고친 check다.

def check(board):
    # 벽돌 갯수 확인 + 시작위치 확인
    brick_count = 0
    top_bricks = [(-1, -1)] * W
    for i in range(H):
        for j in range(W):
            if board[i][j]: brick_count += 1
            # 시작 지점 확인
            if not (top_bricks[j][0] >= 0 or top_bricks[j][1] >= 0) and board[i][j]:
                top_bricks[j] = (i, j)
    return top_bricks, brick_count

#5는 종료 조건과 최솟값 갱신 위치를 옮겨서 고쳤다.

# 구술 발사가 또는 bricks가 전부 소멸되면 마무리
if remain == -1 or bricks <= 0: continue
# (중략)
# 남은 블럭, 다음 시작위치 확인
nxt_starts, cur_bricks = check(cur_board)
min_count = min(min_count, cur_bricks)

여섯 개를 고치고 통과했다.

디버깅에서 남긴 기준

  • 무한루프는 반복문마다 “한 바퀴 돌 때 탈출 조건 쪽으로 반드시 진행하는가”를 본다. 진행이 보장되지 않는 루프가 범인이다( #1 )
  • 다른 분기에 영향을 주는 원인은 두 가지였다. 같은 객체를 여러 분기가 공유하며 수정하는 aliasing( #2 )과, 분기마다 달라야 할 값을 전역에서 읽는 것( #3 )
  • “아직 못 찾음”을 나타내는 기본값은 실제 좌표로 나올 수 없는 값이어야 한다( #6 )

소감

AI 문답에서는 Kruskal의 사이클 판정, Prim의 visited 검사, 다익스트라에 상수를 더하는 변환 모두 결론은 맞혔는데 이유를 설명하려니 비어 있는 곳이 있었다. 반례를 보거나 표를 채우고 나서야 설명이 이어졌다.

그저 수업을 듣는 것 만이 아닌, AI의 추가 질문에 대해 다시 생각해보며 답하니 이해에 많이 도움이 되는 것 같다.