백엔드 개발 파이썬 튜토리얼 깊이 우선 탐색의 언덕을 오르다, Advent of Code day 10

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

Jan 13, 2025 pm 02:09 PM

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

Climbing a depth-first search hill, Advent of Code day 10
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 정의에 따라 역추적하기 전에 각 분기를 완전히 탐색합니다.

Climbing a depth-first search hill, Advent of Code day 10
깊이우선탐색의 시각적 표현

지도 지점은 "노드"이며 한 번에 한 높이씩 올라갑니다. 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 중국어 웹사이트의 기타 관련 기사를 참조하세요!

본 웹사이트의 성명
본 글의 내용은 네티즌들의 자발적인 기여로 작성되었으며, 저작권은 원저작자에게 있습니다. 본 사이트는 이에 상응하는 법적 책임을 지지 않습니다. 표절이나 침해가 의심되는 콘텐츠를 발견한 경우 admin@php.cn으로 문의하세요.

핫 AI 도구

Undresser.AI Undress

Undresser.AI Undress

사실적인 누드 사진을 만들기 위한 AI 기반 앱

AI Clothes Remover

AI Clothes Remover

사진에서 옷을 제거하는 온라인 AI 도구입니다.

Undress AI Tool

Undress AI Tool

무료로 이미지를 벗다

Clothoff.io

Clothoff.io

AI 옷 제거제

Video Face Swap

Video Face Swap

완전히 무료인 AI 얼굴 교환 도구를 사용하여 모든 비디오의 얼굴을 쉽게 바꾸세요!

뜨거운 도구

메모장++7.3.1

메모장++7.3.1

사용하기 쉬운 무료 코드 편집기

SublimeText3 중국어 버전

SublimeText3 중국어 버전

중국어 버전, 사용하기 매우 쉽습니다.

스튜디오 13.0.1 보내기

스튜디오 13.0.1 보내기

강력한 PHP 통합 개발 환경

드림위버 CS6

드림위버 CS6

시각적 웹 개발 도구

SublimeText3 Mac 버전

SublimeText3 Mac 버전

신 수준의 코드 편집 소프트웨어(SublimeText3)

중간 독서를 위해 Fiddler를 사용할 때 브라우저에서 감지되는 것을 피하는 방법은 무엇입니까? 중간 독서를 위해 Fiddler를 사용할 때 브라우저에서 감지되는 것을 피하는 방법은 무엇입니까? Apr 02, 2025 am 07:15 AM

Fiddlerevery Where를 사용할 때 Man-in-the-Middle Reading에 Fiddlereverywhere를 사용할 때 감지되는 방법 ...

10 시간 이내에 프로젝트 및 문제 중심 방법에서 컴퓨터 초보자 프로그래밍 기본 사항을 가르치는 방법? 10 시간 이내에 프로젝트 및 문제 중심 방법에서 컴퓨터 초보자 프로그래밍 기본 사항을 가르치는 방법? Apr 02, 2025 am 07:18 AM

10 시간 이내에 컴퓨터 초보자 프로그래밍 기본 사항을 가르치는 방법은 무엇입니까? 컴퓨터 초보자에게 프로그래밍 지식을 가르치는 데 10 시간 밖에 걸리지 않는다면 무엇을 가르치기로 선택 하시겠습니까?

Inversiting.com의 크롤링 메커니즘을 우회하는 방법은 무엇입니까? Inversiting.com의 크롤링 메커니즘을 우회하는 방법은 무엇입니까? Apr 02, 2025 am 07:03 AM

Investing.com의 크롤링 전략 이해 많은 사람들이 종종 Investing.com (https://cn.investing.com/news/latest-news)에서 뉴스 데이터를 크롤링하려고합니다.

Python 3.6 피클 파일로드 오류 modulenotfounderRor : 피클 파일 '__builtin__'를로드하면 어떻게해야합니까? Python 3.6 피클 파일로드 오류 modulenotfounderRor : 피클 파일 '__builtin__'를로드하면 어떻게해야합니까? Apr 02, 2025 am 06:27 AM

Python 3.6에 피클 파일 로딩 3.6 환경 오류 : ModulenotFounderRor : nomodulename ...

SCAPY 크롤러를 사용할 때 파이프 라인 파일을 작성할 수없는 이유는 무엇입니까? SCAPY 크롤러를 사용할 때 파이프 라인 파일을 작성할 수없는 이유는 무엇입니까? Apr 02, 2025 am 06:45 AM

SCAPY 크롤러를 사용할 때 파이프 라인 파일을 작성할 수없는 이유에 대한 논의 지속적인 데이터 저장을 위해 SCAPY 크롤러를 사용할 때 파이프 라인 파일이 발생할 수 있습니다 ...

See all articles