깊이 우선 탐색의 언덕을 오르다, 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 중국어 웹사이트의 기타 관련 기사를 참조하세요!

핫 AI 도구

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

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

Undress AI Tool
무료로 이미지를 벗다

Clothoff.io
AI 옷 제거제

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

인기 기사

뜨거운 도구

메모장++7.3.1
사용하기 쉬운 무료 코드 편집기

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

스튜디오 13.0.1 보내기
강력한 PHP 통합 개발 환경

드림위버 CS6
시각적 웹 개발 도구

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

뜨거운 주제











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

Linux 터미널에서 Python 사용 ...

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

Pythonasyncio에 대해 ...

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

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

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