코드: 그룹 찾기 + 그룹 활로

지금까지 짠 단일 돌 함수들로는 부족해. 그룹 개념이 들어가니까 BFS (또는 DFS) 가 필요. 시작점에서 인접한 같은 색을 따라가면서 모으는 거.

🔑 BFS 핵심 아이디어

시작점 좌표를 stack (또는 queue)에 넣는다.
stack에서 하나 꺼낸다.
이미 본 거면 패스, 다른 색이면 패스.
같은 색이면 그룹에 추가하고, 인접 4방향을 stack에 넣는다.
stack 빌 때까지 반복.

그리고 그룹 활로는 더 간단해. 그룹의 각 돌에 대해 인접 빈 자리 모으면 끝. set 자료형이라 중복 자동 제거.

실행 결과를 보면:

(2,1)과 (2,2)는 둘 다 같은 그룹 — 둘 다 호출해도 같은 set 반환.
(4,4)는 별개 그룹.
(2,1)-(2,2) 그룹 활로는 6개 (앞 페이지에서 손으로 센 거랑 일치).
(4,4) 모서리 단독 그룹은 활로 2개.

💡 왜 stack을 쓸까

리스트의 pop()은 마지막 원소를 빠르게 꺼낸다. 이게 DFS(깊이 우선)이고, BFS와 동작은 약간 다르지만 그룹 전체를 찾는 결과는 똑같아. collections.deque로 큐를 쓰면 BFS 되고 — 둘 다 정답.

PYTHON

# 그룹을 다루려면 BFS/DFS가 필요해.
# 시작점 → 인접 같은 색 → 또 그 인접 같은 색 → ... 모두 모으기.

EMPTY, BLACK, WHITE = 0, 1, 2
SIZE = 5

def neighbors(r, c):
    """(r,c) 상/하/좌/우 좌표 (보드 안만)"""
    result = []
    for dr, dc in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
        nr, nc = r + dr, c + dc
        if 0 <= nr < SIZE and 0 <= nc < SIZE:
            result.append((nr, nc))
    return result


def find_group(board, r, c):
    """(r,c) 돌이 속한 그룹의 모든 좌표를 set으로 반환.
    빈 자리면 빈 set."""
    if board[r][c] == EMPTY:
        return set()
    color = board[r][c]
    group = set()
    stack = [(r, c)]
    while stack:
        cr, cc = stack.pop()
        if (cr, cc) in group:
            continue
        if board[cr][cc] != color:
            continue
        group.add((cr, cc))
        for nr, nc in neighbors(cr, cc):
            if (nr, nc) not in group:
                stack.append((nr, nc))
    return group


def group_liberties(board, r, c):
    """(r,c) 돌이 속한 그룹의 활로 좌표 set"""
    group = find_group(board, r, c)
    libs = set()
    for cr, cc in group:
        for nr, nc in neighbors(cr, cc):
            if board[nr][nc] == EMPTY:
                libs.add((nr, nc))
    return libs


# 테스트 — 앞 페이지에서 본 그 보드
board = [[EMPTY] * SIZE for _ in range(SIZE)]
board[2][1] = BLACK   # 그룹 1
board[2][2] = BLACK   # 그룹 1 (인접)
board[4][4] = BLACK   # 그룹 2 (떨어짐)

print("=== 그룹 찾기 ===")
print(f"(2,1) 그룹: {sorted(find_group(board, 2, 1))}")
print(f"(2,2) 그룹: {sorted(find_group(board, 2, 2))}")
print(f"(4,4) 그룹: {sorted(find_group(board, 4, 4))}")

print()
print("=== 그룹 활로 ===")
print(f"(2,1)-(2,2) 그룹 활로 수: {len(group_liberties(board, 2, 1))}")
print(f"(4,4) 단독 그룹 활로 수:  {len(group_liberties(board, 4, 4))}")

출력

기대 출력:

=== 그룹 찾기 ===
(2,1) 그룹: [(2, 1), (2, 2)]
(2,2) 그룹: [(2, 1), (2, 2)]
(4,4) 그룹: [(4, 4)]

=== 그룹 활로 ===
(2,1)-(2,2) 그룹 활로 수: 6
(4,4) 단독 그룹 활로 수:  2

← 이전 그룹 — 운명을 공유하는 돌들 다음 → 자살수 — 두면 자기가 죽는 수