깊이 우선 탐색의 언덕을 오르다, Advent of Code day 10

오늘의 챌린지는 6일차와 비슷하지만 여러 경로를 탐색해야 하는 2D 그리드인 10일차 퍼즐을 다룹니다. 이 퍼즐은 깊이 우선 검색(DFS)의 힘을 우아하게 보여줍니다.

AI가 만든 퍼즐 일러스트

지도는 사전으로 표현됩니다. 키는 (x, y) 좌표이고 값은 높이를 나타내는 한 자리 정수(0-9)이며, 9는 최고점을 나타냅니다. 구문 분석 기능은 다음 데이터 구조를 효율적으로 처리합니다.

def parse(input: str) -> dict[tuple[int, int], int | None]:
    return {
        (x, y): int(item) if item.isdigit() else None
        for y, row in enumerate(input.strip().splitlines())
        for x, item in enumerate(row)
    }

트레일은 트레일 시작점(높이 0)에서 정상(높이 9)까지 올라가며 높이가 단계당 정확히 1씩 증가합니다. next_step 함수는 유효한 다음 단계를 식별합니다.

TRAIL_MAX = 9

def next_step(
    topo_map: dict[tuple[int, int], int | None], x: int, y: int
) -> tuple[tuple[int, int], ...]:
    assert topo_map[(x, y)] != TRAIL_MAX

    return tuple(
        incoming
        for incoming in (
            (x + 1, y),
            (x, y + 1),
            (x - 1, y),
            (x, y - 1),
        )
        if (
            isinstance(topo_map.get(incoming), int)
            and isinstance(topo_map.get((x, y)), int)
            and (topo_map[incoming] - topo_map[(x, y)] == 1)
        )
    )

트레일헤드(높이 0)는 find_trailheads:

을 사용하여 위치를 지정합니다.

TRAILHEAD = 0

def find_trailheads(
    topo_map: dict[tuple[int, int], int | None],
) -> tuple[tuple[int, int], ...]:
    return tuple(key for key, value in topo_map.items() if value == TRAILHEAD)

솔루션의 핵심은 깊이우선탐색을 구현한 climb 기능입니다. Wikipedia의 DFS 정의에 따라 역추적하기 전에 각 분기를 완전히 탐색합니다.

깊이우선탐색의 시각적 표현

지도 지점은 "노드"이며 한 번에 한 높이씩 올라갑니다. climb 함수는 DFS 프로세스를 관리합니다.

def climb(
    topo_map: dict[tuple[int, int], int | None], trailheads: tuple[tuple[int, int], ...]
) -> dict[
    tuple[tuple[int, int], tuple[int, int]], tuple[tuple[tuple[int, int], ...], ...]
]:
    candidates: list[tuple[tuple[int, int], ...]] = [(head,) for head in trailheads]

    result = {}

    while candidates:
        current = candidates.pop()
        while True:
            if topo_map[current[-1]] == TRAIL_MAX:
                result[(current[0], current[-1])] = result.get(
                    (current[0], current[-1]), ()
                ) + (current,)
                break

            elif steps := next_step(topo_map, *current[-1]):
                incoming, *rest = steps

                candidates.extend([current + (step,) for step in rest])

                current = current + (incoming,)
            else:
                break

    return result

else 절의 break은 막다른 골목을 처리하여 무한 루프를 방지합니다. 이 함수는 각 트레일 기점에서 정상까지의 모든 경로를 반환합니다.

1부에서는 고유한 최고 목적지를 계산합니다.

def part1(input: str) -> int:
    topo_map = parse(input)

    return len(climb(topo_map, find_trailheads(topo_map)))

2부에서는 모든 고유 경로를 계산합니다.

def part2(input: str) -> int:
    topo_map = parse(input)

    return sum(
        len(routes) for routes in climb(topo_map, find_trailheads(topo_map)).values()
    )

대체 접근 방식(예: 트레일 시작 부분 감지를 구문 분석에 통합)이 존재하지만 이 솔루션의 성능은 괜찮습니다. 최근 구직 활동의 실패로 인해 내 기분이 꺾이지는 않았습니다. 나는 여전히 희망적이다. 중급 Python 개발자를 찾고 있다면 연락하세요. 다음주까지!

위 내용은 깊이 우선 탐색의 언덕을 오르다, Advent of Code day 10의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!