코드: 집 찾기 (BFS 또 등장)

알고리즘 흐름:

아직 안 본 빈 자리를 찾는다.
거기서 BFS로 연결된 모든 빈 자리를 모은다 (이게 한 "영역").
BFS 도중 만나는 돌은 border_colors set에 색깔 기록.
BFS 끝났을 때 border_colors가 한 색만 있으면 그 색의 집. 두 색이면 중립.

그룹 찾기(Ch 3)와 매우 비슷하지만, 이번엔 빈 자리를 묶고, BFS 도중 만난 돌은 묶지 않고 색만 기록.

💡 알고리즘 패턴이 반복된다

이게 그래프 탐색의 위력. 한 번 BFS를 익히면 "연결된 무엇을 묶는 모든 문제"에 쓸 수 있어. 그룹 찾기, 집 찾기, 그리고 PART 3의 MCTS 트리 탐색까지 — 결국 다 그래프 탐색이야.

PYTHON

# 보드를 분석해서 각 빈 영역의 소유자를 판정한다.
# Ch 3의 BFS 패턴이 또 등장 — 단, 이번엔 "빈 자리"를 묶는다.

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

def neighbors(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_territories(board):
    """모든 빈 영역을 묶고, 각 영역의 소유자 판정.
    반환: {'black': [...좌표 리스트], 'white': [...], 'neutral': [...]}"""

    visited = set()
    result = {'black': [], 'white': [], 'neutral': []}

    for r in range(SIZE):
        for c in range(SIZE):
            if (r, c) in visited or board[r][c] != EMPTY:
                continue

            # BFS: 연결된 빈 영역과 그 외곽 색깔 모음
            region = set()
            border_colors = set()
            stack = [(r, c)]

            while stack:
                cr, cc = stack.pop()
                if (cr, cc) in region:
                    continue
                if board[cr][cc] == EMPTY:
                    region.add((cr, cc))
                    visited.add((cr, cc))
                    for nr, nc in neighbors(cr, cc):
                        stack.append((nr, nc))
                else:
                    # 빈 영역 가장자리의 돌 색깔 기록
                    border_colors.add(board[cr][cc])

            # 한 색만 인접 → 그 색의 집. 두 색 → 중립.
            if border_colors == {BLACK}:
                result['black'].extend(region)
            elif border_colors == {WHITE}:
                result['white'].extend(region)
            else:
                result['neutral'].extend(region)

    return result


# === 테스트: 앞 페이지의 보드 ===
board = [[EMPTY] * SIZE for _ in range(SIZE)]
# 흑돌 1행
for c in range(SIZE):
    board[1][c] = BLACK
# 백돌 3행
for c in range(SIZE):
    board[3][c] = WHITE

t = find_territories(board)
print(f"흑집 {len(t['black'])}개: {sorted(t['black'])}")
print(f"백집 {len(t['white'])}개: {sorted(t['white'])}")
print(f"중립 {len(t['neutral'])}개: {sorted(t['neutral'])}")

출력

기대 출력:

흑집 5개: [(0, 0), (0, 1), (0, 2), (0, 3), (0, 4)]
백집 5개: [(4, 0), (4, 1), (4, 2), (4, 3), (4, 4)]
중립 5개: [(2, 0), (2, 1), (2, 2), (2, 3), (2, 4)]

← 이전 집 시각화 다음 → 코드: 점수 계산 + 덤